https://codeforces.com/contest/1330/problem/D
给出d,m, 找到一个a数组，满足以下要求：
a数组的长度为n,n≥1;
1≤a1<a2<⋯<an≤d；
定义一个数组b：b1=a1, ∀i>1,bi=bi−1⊕ai ，并且 b1<b2<⋯<bn−1<bn ；
求满足条件的a数组的个数并模m；
人话：求一个a数组满足递增，并且异或前缀和也递增 ，求出a数组个数mod m。
太菜了，不会，看了很多题解才会的，这里总结一下：
参考官方题解 https://codeforces.com/blog/entry/75559
首先思考数组递增并且前缀异或和也递增(异或运算：不进位加法 1^1=0,1^0=1,0^0=0)，那么就必须满足后面一个数二进制的最高位1的位置大于前面一个数的二进制的最高位1的位置，我们来看下为什么，假如最高位和前一个相同，那么前缀异或和最高位的1就消掉了，肯定会变小，最高位比前一个低，那这个数就比前一个数小了，不满足数组递增，所以要比前一个数的最高位高。
每个数1的最高位 h(ai)=v, v代表ai的最高位，例如：h(1)=0，h(2)=h(3)=1， and h(4)=h(7)=2。
找出每个最高位的个数，例如 h(ai)=v，ai的最高位为v，找到最高位为v的区间，[2v,2(v+1)−1] ,还要注意一个边界问题，不能大于d，所以为：[2v,min(2(v+1)−1,d)],那么个数就为 min(2(v+1)−1,d)-2v+1，最后再加上不选的一种情况，最后为min(2(v+1)−1,d)-2v+1+1。然后分组，把最高位相同的分在一起，每一次都从一个组里面选择一个数或者不选，来组成a数组，就是把每个最高位的个数都乘起来（不选的情况我把它算进最高位的个数里面了），再减掉全部不选的情况，就好了。
例如：d=6,最高位为0的有1个，那么我们有两种选择，选1或者不选；最高位为1的有2个，那么我们有三种选择，选2或者3或者不选，最高位为2的有3个，那么我们有四种选择，选4或者5或者6或者不选；然后组合在一起，里面有全部不选的一种情况，所以最后结果要减1，即：2*3*4-1=23.
写得很啰嗦，因为我看了好久才看懂 ~~
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+;
const int mod=1e9+;
typedef long long ll;
//typedef __int128 LL;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll d,m;
scanf("%lld%lld",&d,&m);
ll ans=;
for(int i=;i<=;i++)
{
if(d<(<<i))break;
ans=(ans*(min(d,(1ll<<(i+))-)-(<<i)++))%m;
}
ans--;
if(ans<)ans+=m;
printf("%lld\n",ans);
}
return ;
}
还有一种递推的方法，参考博客：https://www.cnblogs.com/AaronChang/p/12635428.html
用一个cnt[i]数组来记录每个最高位的个数，每次选择了一个数之后就从后面的数中选择；
dp[i]表示二进制的最高位1在前i位（包含第i位）的方案数之和，dp[i]=dp[i-1]+dp[i-1]*cnt[i]+cnt[i] ,（只单独取cnt[i]也可以）
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+;
const int mod=1e9+;
typedef long long ll;
//typedef __int128 LL;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
ll dp[],cnt[];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
ll d,m;
scanf("%lld%lld",&d,&m);
ll a=d,idx=,t=;
while(a)
{
cnt[++idx]=min(d-(t-),t);//下标从1开始，方便dp数组
t<<=;
a>>=;
}
for(int i=;i<=idx;i++)dp[i]=((dp[i-]+(dp[i-]*cnt[i])%m)%m+cnt[i])%m;
printf("%lld\n",dp[idx]);
}
return ;
}