Codeforces Round #631 (Div. 2) D.Dreamoon Likes Sequences
题意：给你d和m，让你构造一个递增数组a，使数组b（i==1,b[i]=a[i] ; i>1, b[i]=b[i-1]^a[i]）递增，求a有几种，答案模m。
题解：根据异或的性质可以得出：2后边不能有3, 4后边不能有5~7, 8后边不能有9~15...... 然后就很好写了。用数组b记录第i个数可以取得数有多少个，数组dp记录长度为 i 的 a 数组有几种。看下边的代码应该就清楚了。
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 ll dp[100]; 6 ll b[100]; 7 8 int main() 9 { 10 ll t; 11 cin>>t; 12 while(t -- ){ 13 memset(b,0,sizeof(b)); 14 memset(dp,0,sizeof(dp)); 15 ll d,m; 16 cin>>d>>m; 17 ll x = d; 18 ll s = 1,k = 1; 19 while(x){ 20 b[k ++ ] = min(s,d - s + 1); //第k个数的取法 21 //s是当前位可以取的个数，d-s+1是最大到d还可以取的个数 22 x >>= 1; 23 s <<= 1; 24 } 25 for (ll i= 1; i< k; ++i ) 26 dp[i] = (dp[i - 1]%m + b[i] % m + dp[i - 1] * b[i] % m) % m; //只有i-1位+只有最后一位+（i-1位的个数）*（第i位个数） 27 cout<<dp[k-1]<<endl; 28 } 29 return 0; 30 }
