【算法】trie
【题解】
为了让数据有序，求lowbit无法直接排序，从而考虑倒过来排序，然后数据就会呈现出明显的规律：
法一：将数字倒着贴在字典树上，则容易发现两数的lowbit就是它们岔道结点的深度，所以先建树后对于一个数字依次把每次分岔开的另一边的size乘上权值累加答案。
法二：从高位到低位分组求和，即第一位1在上，0在下，则两边之间互相计算过后就再无影响，只剩下各自内部的事情再处理。由于排序后数据的有序性使分治可行。
法三：排序后对于一个数字，它和后面的数字的lowbit有单调性……然后可以维护它，相当麻烦，不再赘述。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=,MOD=; int size[maxn*],t[maxn*][],tot,a[maxn],n;
void insert(int x,int dep,int num)
{
if(dep>)return;
if(t[x][num&])
{
size[t[x][num&]]++;
}
else
{
t[x][num&]=++tot;
t[t[x][num&]][]=t[t[x][num&]][]=;
size[t[x][num&]]=;
}
insert(t[x][num&],dep+,num>>);
}
int query(int x,int dep,int num)
{
if(dep>)return ;
long long ansnow=((t[x][(num&)^]?size[t[x][(num&)^]]:)<<dep)%MOD;
if(t[x][(num&)])ansnow=((ansnow+query(t[x][num&],dep+,num>>)))%MOD;
return (int)(ansnow%MOD);
}
int main()
{
int T,now=;
scanf("%d",&T);
long long ans=;
while(T--)
{
now++;
tot=;
t[][]=t[][]=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
insert(,,a[i]);
}
ans=;
for(int i=;i<=n;i++)ans=(ans+query(,,a[i]))%MOD;
printf("Case #%d: %d\n",now,(int)(ans%MOD));
}
return ;
}