$#C240725B. 异或(xor)
网址（Website）
题解（Solution）
$\qquad$令 $mx=max_{i=1}^𝑛𝑎_𝑖$ 。 首先相等的数可以去重，因此更新 $a_i$ 为去重后的数组，$c_i$ 为值为 $a_i$ 的数的个数。
$\qquad$令 $g_i$表示满足 $f([s_1,s_2,\cdots,s_k])=i$ 的序列数量，则最终答案为 $\sum_{i=1}^{∞}g_i$ ，容易发现 ${g_i}$ 最多计算到 ${mx*2}$。
$\qquad$考虑计算 $g_i$ 。令 $highbit (𝑥)$ 表示 $𝑥$ 转为二进制后最高位 $1$ 的位置。不难发现对于任意 $x,y$ ，若 $⌊\frac{ 𝑎_x}{2^{highit (𝑖)+1}}⌋≠⌊\frac{𝑎_y}{2^{highbit (𝑖)+1}}⌋$，则一定有 $a_x⊕a_y ≥ i$ 。
$\qquad$这鼓励我们同时计算出 $𝑖\in[2^{k},2^{𝑘+1})$ 的 $g_i$ 。由于上面的性质，我们考虑将每个数二进制下的后 $k$ 位除去（即 $a_*=\lfloor \frac{a_*}{2^{k}}\rfloor$），再将每个 $a_*$ 相同的分到一组；如果两个组存的数满足 $⌊\frac{𝑎∗}{2^{𝑘+1}}⌋$ 相等，那么这两个组必定是高位相同、二进制下的第 $k$ 位不同的两个组，我们把这种组称为一对组。
$\qquad$对于每对组，首先每个组内不可能选两个数及以上，因为组内的数一定满足 $⌊\frac{a_x}{2^k}⌋=⌊\frac{a_y}{2^k}⌋$ ，则组内任两个数的异或值一定小于 $2^k$ ，而我们要计算的是 $[2^{k},2^{𝑘+1})$ 的答案，所以，合法的序列数只能在一对组的两个小组中各选一个算得，这样两个数的异或值一定在 $[2^𝑘,2^{𝑘+1})$ 范围内。我们可以暴力枚举选哪两 个数，因为每对数恰好被计算一次，因此复杂度是 $O(n^2)$ 的。
$\qquad$除了合法的方案数，我们还需要统计不合法的（即异或值大于等于 $2^{k+1}$ 的数），当且仅当每队组中只选出一个数时或不选时，根据之前的推理，这个时候选出来的数与其他数的异或值一定大于等于 $2^{k+1}$ 。
$\qquad$注意题目中 $∣S∣≥2$ 的限制，因此在合并答案时还需要做一个小背包，具体细节见代码。
$\qquad$总时间复杂度 $O(n^2\log m)$ 。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
//#define int long long
#define fi first
#define se second
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f;
const int N = 3012345;
vector<int> g[N];
long long a[N],c[N];
long long n,nn,mod,ans;
long long mx,l2;
int f[N],f1[N],h[N];
//f[i]: 表示 要计算 f(s)异或和 为 i 的序列个数，可被看作背包里面的 f[i][j]
//f1[N]:表示 之前 f(s)异或和 为 i 的序列个数，可被看作背包里面的 f[i-1][j]
//h[N]: 表示 当前组 f(s)异或和 为 i 的序列个数
//特别的，f[1<<i+1] 和 h[1<<i+1]
//表示构成的 f(s)异或和 大于 [2^i, 2^(i+1)] 范围内的方案数
//这些方案可以和任何的 f(s)异或和 为 i 的方案匹配，且不影响最后异或答案
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string str("xor");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
cin>>n>>mod;int Tim = clock();
For(i,1,n) a[i] = input(), mx = max(a[i],mx);
while((1<<l2)<mx) ++l2;
mx*=2;//计算最高位数
sort(a+1,a+n+1),a[0] = -1;
For(i,1,n) if(a[i]!=a[nn]) a[++nn]=a[i],c[nn]=1; else ++c[nn];
For(i,0,l2){//枚举每一位并计算[2^i, 2^(i+1))范围对答案的贡献
For(j,0,mx>>i) g[j].clear();
For(j,1,nn) g[a[j]>>i].emplace_back(j);//将 a[i] 按高位分组
f[1<<i]=0, f[1<<(i+1)]=1;//空集也算作一种方案
For(j,0,mx>>(i+1)){//枚举，注意这里多除了一个 2，在后面有用
For(k,(1<<i),(1<<(i+1))) f1[k]=f[k], h[k]=0;
//这里的 j<<1 和 j<<1|1 可以将当前这一位分成 1和 0 两组
//只有高位相同且当前位不同时，异或出来的答案在[2^i, 2^(i+1)]区间内
for(int x:g[j<<1]) for(int y:g[j<<1|1])
(h[a[x]^a[y]] += 1ll*c[x]*c[y]) %= mod;
h[1<<(i+1)] = 1;
for(int x:g[j<<1]) h[1<<(i+1)] += c[x];
for(int y:g[j<<1|1]) h[1<<(i+1)] += c[y];
//原本是求 f[min(i,j)] += f1[i] * h[j]，
//转化为求 f[i] += f1[i] * SUM(h[j]) ------ j>i
// f[j] += SUM(f1[i]) * h[j] ------ j<i
// f[i] += f1[i] * h[i] ------ j=i
long long x=0,y=0;
Rof(k,1<<(i+1),1<<i) f[k] = (1ll*f1[k]*y + 1ll*x*h[k] + 1ll*f1[k]*h[k])%mod, (x+=f1[k])%=mod, (y+=h[k])%=mod;
}For(k,1<<i,(1<<(i+1))-1) (ans+=1ll*f[k]*k) %= mod;//异或和为k的序列数*每一种的贡献
}cout<<(ans+mod)%mod<<'\n';
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
