https://codeforces.com/contest/1330/problem/D
题意:
数组 \(a_i\) 严格递增,\(1\le a_i \le n\) 。用 \(a_i\) 构造 \(b_i\): \(b_1=a_1\); \(b_i = b_{i-1}\) \(xor\) \(a_i\)。要求 \(b_i\) 也严格递增。问这样的数组 \(a_i\) 有多少
思路:
如果相邻两个 \(a_i\) 的二进制最高位相同,那么 \(b_i\) 将失去这一位。所以每个 \(a_i\) 的最高位都要不同
记最右边为第 \(0\) 位,则 \(n\) 的最高位为 \(d=log_2(n)\) 。可以这样构造出 \(a_i\) :选1或0个最高位为 \(0\) 的数,再选1或0个最高位为 \(1\) 的数,一直选到 \(d\) 位
“选1或0个最高位为 \(i\) 的数” 有 \(2^i+1\) 种可能,“选1或0个最高位为 \(d\) 的数” 有 \((n-(1<<d)+1)+1\) 种可能。全部乘起来即可。注意全都选0个是不行的,所以 ans-1
#include <bits/stdc++.h>
using namespace std;
signed main()
{
int T; cin >> T; while(T--)
{
int n, m; cin >> n >> m;
int d = log2(n), ans = 1;
for(int i = 0; i < d; i++)
ans = 1ll * ans * (((1<<i)+1) % m) % m;
ans = 1ll * ans * ((n - (1<<d) + 2) % m) % m;
cout << (ans-1+m)%m << '\n';
}
return 0;
}