Dreamoon Likes Sequences CodeForces - 1330D（组合数学+位运算）

Dreamoon likes sequences very much. So he created a problem about the sequence that you can’t find in OEIS:

You are given two integers d,m, find the number of arrays a, satisfying the following constraints:

The length of a is n, n≥1
1≤a1<a2<⋯<an≤d
Define an array b of length n as follows: b1=a1, ∀i>1,bi=bi−1⊕ai, where ⊕ is the bitwise exclusive-or (xor). After constructing an array b, the constraint b1<b2<⋯<bn−1<bn should hold.
Since the number of possible arrays may be too large, you need to find the answer modulo m.

Input
The first line contains an integer t (1≤t≤100) denoting the number of test cases in the input.

Each of the next t lines contains two integers d,m (1≤d,m≤109).

Note that m is not necessary the prime!

Output
For each test case, print the number of arrays a, satisfying all given constrains, modulo m.

Example
Input
10
1 1000000000
2 999999999
3 99999998
4 9999997
5 999996
6 99995
7 9994
8 993
9 92
10 1
Output
1
3
5
11
17
23
29
59
89
0
题意：
给出一个限制 d 与模数 mod ，求出可以构造出的满足条件的数组 a 的个数，需要满足以下条件：
①数组 a 的长度大于等于 1
②数组 a 严格递增
③数组 a 的最小值大于等于 1 ，数组 a 的最大值小于等于 d
对于数组 a ，构造出一个数组 b ：
i == 1 时：b[ 1 ] = a[ 1 ]
i > 1 时：b[ i ] = b[ i - 1 ] ^ a[ i ]
数组 b 严格递增。
思路：牵扯到异或，我们就要考虑位运算了。对于a数组的每一个数，如果它选择了2，那么它接下来就没有办法选择3；如果它选择了4，那么它接下来就没有办法选择5,6,7；如果它选择了8，那么它接下来就没有办法选择9,10,11,12,13,14,15.换句话说，最高位为i的数字只能出现一次。那么第i位可以选择的数量为，但是第i位还有可能不加，也就是在原来基础上加1.然后累乘就可以了。最后结果要减一，这代表的是所有位都没有选择数的情况。
代码如下：

#include<bits/stdc++.h> #define ll long long using namespace std;int n,mod;int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&mod);ll ans=1;for(int i=0;i<30;i++){if((1<<i)>n) break;ans=(ans*(min((1<<(i+1))-1,n)-(1<<i)+2));ans%=mod;}ans=(ans-1+mod)%mod;cout<<ans<<endl;}return 0; }

努力加油a啊，(^o)/~

总结

以上是生活随笔为你收集整理的Dreamoon Likes Sequences CodeForces - 1330D（组合数学+位运算）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。