思路
首先要明白b数组，其实就是a数组的异或前缀和，那么要怎么保证异或递增？选的数拆成二进制之后肯定需要位数递增才行，所以我们考虑把d拆成2进制，分成很多块儿，就是这样
[1],[10,11],[100,101,110,111],[1000,….],….
分成上面这样的块，然后从这里面找序列就可以了，然后发现这些块的大小是1 2 4 8 16这样的，然后问题就变成了从x个块中分别取1,2,3,4,5~x个数，然后得到的sum，发现这些数都是2的次幂对吧，我们就找它的系数。它的系数应该怎么找的？考虑当$2^k$为最高的位置时，例如$2^2$在第三位的时候，前面可以有$[2^0,2^1,2^2]$这样如果在第二位就有$[2^0,2^2]与[2^1,2^2]$，然后它的系数就是在它前面的和。接下来这样还是不太好求它的系数，但是我们发现如果从低到高的求系数的话，就可以使用前面的信息，例如当我求出$2^1$的系数为2,也就是$[2^0,2^1]以及[2^1]$本身，还有$2^0$的系数为1，也就是[2^0]自身，那么$2^2$的系数就相当于在它前面出现过的序列相加啊，也就是$[2^0,2^1],[2^1],[2^0]$的后面加上$[2^2]$，也就变成$[2^0,2^1,2^2],[2^1,2^2],[2^0,2^2]$所以我们可以直接递增的求出系数6来。当然它可能不一定是整块，最后剩余的部分怎么考虑？前面有x-1块，处理完后，我们就在这些序列的后面直接加上yu的话，也就是多了这些序列*yu的序列，然后还有后面一部分自成序列的情况，也就是再+yu即可。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N=35;
int fac[N];
inline bool isprime(ll num)
{if(num==2||num==3)return true;
if(num%6!=1&&num%6!=5)return false;
for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
fac[0]=1;
int d,m;
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&d,&m);
for(int i=1;i<=32;i++)fac[i]=1ll*2*fac[i-1]%m;
int lim = 0;
ll ans = 0;
while((1ll<<lim)<=d+1)lim++;
ll yu = d-(1ll<<(lim-1))+1;
ll add=1;
for(int i=1;i<lim;i++){
ans+=1ll*add*fac[i-1];
add+=1ll*fac[i-1]*add;
add%=m;
ans%=m;
}
ans=(ans*(yu+1)+m)%m;
ans=(ans+yu+m)%m;
printf("%lld\n",ans);
}
}
|