Magic题解
题意简述：
给定\(n\)个数\(a_1,a_2,…,a_n\)，设对于数\(x\)，\(|x|\)表示其在十进制下的位数，也即\(10^{|x|}\le x<10^{|x|+1}\)
需要计算：
\[\sum_{i=1}^n\sum_{j=i+1}^na_i\oplus a_j \]数据范围：
\(n\le 5\times 10^4,a_i\le 10^{18}\)
分析
这个数据范围启发我们设计一个带\(\log\)的算法
如果我们设
\(S_k=\)\(\sum_{i=1}^n\sum_{j=i+1}^n[a_i\oplus a_j\ge k]\)
则我们要求解的答案是：
\[\sum_{k=1}^{18}k(S_{10^k}-S_{10^{k+1}})+\frac{n(n-1)}{2}=S_0+S_{10}+…+S_{10^{18}} \]所以问题转化为求解\(S\)
关于异或的问题，不难想到使用字典树进行求解，设我们已经将所有的\(a\)插入到字典树中。
数据范围是允许我们将求解每一个\(S\)的复杂度为\(O(n\log n)\).这正好就是在字典树中遍历\(n\)个数的复杂度。
这启发我们设计函数solve(s,t)表示对于\(s\)计算其对\(S_t\)的贡献。
设\(s,t\)的二进制表示分别为\((b_k,b_{k-1}…b_1),(c_k,c_{k-1}…c_1)\)
对于答案的计算，可以将其分为两部分：可以在当前位解决的和留在后续解决的。
则我们设指针\(p\)从\(k\)遍历到\(1\)，按位统计贡献，将这个过程看作我们不断填数的过程，设所填数为\(x\)，其二进制表示为\((d_k,d_{k-1}…d_1)\)
分类讨论：
- \(b_p=1,c_p=1\)。此时，我们若想要保持\(x\oplus s>t\)的可能，就需要让\(x\oplus s\)的第\(p\)位为1，也即我们填上\(d_p=0\)，此时我们无法计算出答案
- \(b_p=0,c_p=1\)，类比情况一，填上\(d_p=1\)
- \(b_p=1,c_p=0\)，此时我们将\(d_p\)填为\(1/0\)，当填为\(0\)时，第\(p-1\sim 1\)位无论填什么都可以对答案产生贡献，所以直接累加上\(siz[t[p][0]]\)的贡献并将\(d_p\)填为\(1\)即可。
- \(b_p=0,c_p=0\)，类比情况三，可以得到算上\(siz[t[p][1]]\)的贡献然后将\(d_p\)填为0即可。
核心代码：
int solve(int s,int tt){//在trie中查找与s异或比t大的数的数量
int p=1,ans=0;
for(int i=60;i>=0;i--){
if(!p)return ans;
int x=(s>>i)&1;
if((tt>>i)&1){
p=t[p][x^1];
}
else{
ans+=siz[t[p][x^1]];
p=t[p][x];
}
}
return ans;
}