头条编程笔试题：异或(01字典树)

链接：https://www.nowcoder.com/questionTerminal/fc05f68c5f47438db54c6923ef23cf4a?orderByHotValue=0&commentTags=Python
来源：牛客网
 

给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。

输入描述:

第一行包含两个整数n,m. 

第二行给出n个整数A1，A2，...，An。

数据范围

对于30%的数据，1 <= n, m <= 1000

对于100%的数据，1 <= n, m, Ai <= 10^5

输出描述:

输出仅包括一行，即所求的答案

示例1

输入

3 10  
6 5 10

输出

2

AC code：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e6+1;
int sz;
int ch[maxn][2];
LL val[maxn];//前缀个数
LL a[maxn];
int n;
LL m,ans;

void init()
{
    sz=1;
    memset(ch,0,sizeof(ch));
    memset(val,0,sizeof(val));
}

void _insert(LL x)
{
    int u=0;
    for(int i=32;i>=0;i--)
    {
        int c=(x>>i)&1;
        if(!ch[u][c])
        {
            ch[u][c]=sz++;
        }
        u=ch[u][c];
        val[u]++;
    }
}

LL query(LL x,LL m)//查找数组里任意两个元素的异或值大于m的个数
{
    int u=0;
    LL res=0;
    for(int i=32;i>=0;i--)
    {
        int c=(x>>i)&1;
        int d=(m>>i)&1;
        if(d==0)//使第i位为1必定大于m
        {
            if(ch[u][c^1]&&val[ch[u][c^1]])
            {
                res+=val[ch[u][c^1]];
            }
            u=ch[u][c];
        }
        else
        {
            u=ch[u][c^1];
        }
        if(val[u]==0)
            break;
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        _insert(a[i]);
    }
    
    ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=query(a[i],m);
    }
    printf("%lld\n",ans/2);
    return 0;
}