CF 1329B Dreamoon Likes Sequences

题目：

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.

思路：容易想到如果两个数二进制的最高位都是1，则两者"^"后者数值一定比前者小，可以推断出"2^0 ~ 2^1 - 1","2^1 ~ 2^2 - 1",...,"2^(n-1) ~ 2^(n) - 1"为不同集合，我们只需要统计出每个集合的个数，然后求出组合方案数就行。

 #include<iostream>

 #include<string>

 #include<vector>

 #include<cstdio>

 #define ll long long

 #define pb push_back

 using namespace std;

 const int N = 1e6 + ;

 vector<ll > a;

 ll p[N];

 ll ans, MOD;

 void init()

 {

     int x = ;

     while(){

         p[x] = ( << x) - ;

         if(p[x] > 1e9) break;

         x++;

      }

 }

 void solve()

 {   

     init();

     int T;

     cin >> T;

     while(T--){

         ans = ;

         a.clear();

         ll n;

         cin >> n >> MOD;

         int inx = -;

         for(int i = ; i < ; ++i){

             if(n >= p[i]) a.pb(p[i] - p[i - ]);

             else{

                 inx = i;

                 break;

             }

         }

         if(n - p[inx - ] > ) a.pb(n - p[inx - ]);

         for(auto x : a){

             ans = (ans * (x + )) % MOD;

         } 

         ans = (ans -  + MOD) % MOD;

         //cout << "(ans = " << ans << ")" << endl;

         cout << ans << endl;

     }

 }

 int main() {

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     solve();

     //cout << "ok" << endl;

     return ;

 }

巴特西

CF 1329B Dreamoon Likes Sequences

最新文章

热门文章