题目链接：
hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5269
bc:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=603&pid=1002
题解：
（以下有提到位数的都是指二进制表示）
对于xor值为1的两个数，他们的最低位（二进制表示）必然不同，所以我们把n个数按最低位数不同分为两堆，这两堆个数的乘积就是xor的值等于1的贡献。同理，我们可以递归处理出xor值等于2,4,8，16...2^30的贡献值，然后把它们加起来。
一种做法是类似快速排序先按最低位数排序，0的在左边，1的在右边，算完2^0的贡献之后，再递归算全0的那块，全1的那块中2^1的贡献，依次类推。不过这种做法的缺陷是最坏情况下时间复杂度会变为n^2；
一种高效的做法是用一颗trie树来维护，把每个数从最低位开始按每一位的01取值存到trie树上，这样某一位为零的都会在左子树上，为1的都会在右子树上。这样离线处理好就不用我们每一次递归的时候去维护了.
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const int maxn=+;
const int mod=;
typedef long long LL; struct Trie{
int ch[maxn*][],tot;
int val[maxn*];
void init(){
val[]=;
memset(val,,sizeof(val));
memset(ch[],,sizeof(ch[]));
tot=;
}
void insert(int x){
int p=;
for(int i=;i<;i++){
int tmp;
if((<<i)&x) tmp=;
else tmp=;
if(!ch[p][tmp]){
memset(ch[tot],,sizeof(ch[tot]));
ch[p][tmp]=tot++;
}
p=ch[p][tmp];
val[p]++;
}
}
void query(int cur,int h,LL &ans){
int lef=ch[cur][],rig=ch[cur][];
LL tmp=(LL)val[lef]*val[rig]%mod*(<<h)%mod;
// printf("tmp:%d\n",tmp);
ans+=tmp;
ans%=mod;
if(lef) query(lef,h+,ans);
if(rig) query(rig,h+,ans);
}
}trie; int n; void init(){
trie.init();
} int main(){
int tc,kase=;
scanf("%d",&tc);
while(tc--){
init();
scanf("%d",&n);
for(int i=;i<n;i++){
int x;
scanf("%d",&x);
trie.insert(x);
}
// for(int i=0;i<22;i++) printf("val:%d\n",trie.val[i]);
LL ans=;
trie.query(,,ans);
printf("Case #%d: %lld\n",++kase,ans*%mod);
}
return ;
}