Team Formation---zoj3870（异或）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5518

　　题意就是有n个数，如果满足a^b > MAX(a, b),就算一种组合，问n个数之间这样的组合有多少个；

　　可以发现，如果要让一个数增大，只要该数化为二进制后的出现0的位置跟1异或就会变大，

　　同时需要满足另一个数的最高位为该数出现0位置的位数，

　　如10可以跟1异或变为11 ，100可以跟10、11、1异或分别变为110,111,101,而101只能跟两位的进行异或，

　　因为它的0出现的位置为第二位，最后求和就行了。

　　cnt[i]代表a数组都转换成二进制数后最高位所在位置i为1的数的个数；

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cstdlib>

using namespace std;

#define N 100010

int a[N];

int main()

{

    int T, b[], cnt[], ans, n;

    scanf("%d", &T);

    while(T--)

    {

        memset(a, , sizeof(a));

        memset(cnt, , sizeof(cnt));

        scanf("%d", &n);

        for(int i=; i<n; i++)

            scanf("%d", &a[i]);

        sort(a, a+n);

        ans=;

        for(int i=; i<n; i++)

        {

            int j=;

            while(a[i])

            {

                b[j++] = a[i]%;

                a[i]/=;

            }

            for(int k=; k<j; k++)

            {

                if(b[k]==)

                    ans+=cnt[k];///表示首位是这个位置的并且为1的，0与之异或一定变大；

            }

            cnt[j-]++;///让该位置为1的个数加1；

        }

        printf("%d\n", ans);

    }

    return ;

}