题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6059

题意：如题。

解法：这道题，赛后一时没有懂，今天拿出来看了题解，瞬间懂了，开深。我把自己对这道题的理解写一下。


1，需要做什么？我们需要枚举数字的每一位，建立一个前缀字典树，sum【】记录这个节点添加的个数，x【】代表不符合要减去的个数，tot【i】【j】代表第i位的第j位的 数量。


2，怎么做？枚举a[k]的每一位，对于a[k]的第cur位Kcurp,如果Kcurp等于1的话，那么对答案产生贡献的Icurp和Jcurp（Icurp代表a[i]的第cur位,Jcurp代表a[j]的第cur位）一定为0，而且a[i]的前cur位和a[k]的前cur位必定相同，这个自己推一推就明白了,然后再记一下a[Kcurp]对应的节点为p,同父亲的另一个儿子对应pp。


那么如何计算答案？


3，如果从0-Kcurp的 每一位，a[i],a[j],a[k]都相等时，ak[Kcurp]加入后贡献是sum[p]*(sum[p]-1)/2.


4,ai【0】-ai【Kcurp-1】和aj【0】-aj【Kcurp-1】有部分不想等，ai【0】~ai【Kcurp-1】和ak【0】~ak【Kcurp-1】相等时，贡献是sum[p]*(tot[i][b[i]^1]-sum[p])-x[p]。（下面说x[p]）


5，x【p】表示加入一个点，产生的不合法贡献，就是tot[i][b[i]]-sum[pp].


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 500010;
const int maxs = 35;
int T,n,b[maxs];
int cnt,sum[maxn*maxs],ch[maxn*maxs][2],tot[maxs][2];
LL ans,x[maxn*maxs];
void insert()
{
    int now = 0;
    for(int i = 0; i < 31; i++){
        int go = b[i];
        if(!ch[now][go]){
            ch[now][go] = ++cnt;
            memset(ch[cnt], 0, sizeof(ch[cnt]));
            x[cnt] = sum[cnt] = 0;
        }

        //cal answer
        int p = ch[now][go^1], pp = ch[now][go];

        ans += 1LL*sum[p]*(sum[p]-1)/2;

        ans += 1LL*sum[p]*(tot[i][go^1]-sum[p])-x[p];

        x[pp] += tot[i][go] - sum[pp];

        sum[pp]++;

        tot[i][go]++;

        now = ch[now][go];
    }
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        cnt = 0;
        ans = 0;
        sum[0] = x[0] = 0;
        memset(tot, 0, sizeof(tot));
        memset(ch[0], 0, sizeof(ch[0]));
        for(int i=1; i<=n; i++){
            int v;
            scanf("%d", &v);
            for(int j=30; j>=0; j--){
                b[j] = v&1;
                v >>= 1;
            }
            insert();
        }
        printf("%lld\n", ans);
    }
    return 0;
}