CF1329B. Dreamoon Likes Sequences

发表于 | 阅读数

构造$1\leq a_1<..a_x\leq d$ 数列。使得$a_1\leq a_1 \oplus a_2<…a_1\oplus..a_n$

建议打表，就可以看出规律

二进制$01XXX$不能存在$O1XXX$显然异或之后会变小，导致后面也会变小所以再每组$[2^i,2^{i+1})$里面选一个，乘法原则即可。

代码 
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


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int d, m, ans;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> d >> m;
        ans = 1;
        for (int i = 0; (1 << i) <= d; i++)
        {
            int p = min((1 << i), d - (1 << i) + 1);
            ans = 1ll * (p + 1) * ans % m;
        }
        printf("%d\n", (ans + m - 1) % m);
    }
}