链接：https://ac.nowcoder.com/acm/contest/881/H
来源：牛客网
 

题目描述

Bobo has a set A of n integers a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​.
He wants to know the sum of sizes for all subsets of A whose xor sum is zero modulo (109+7)(10^9+7)(109+7).
Formally, find (∑S⊆A,⊕x∈Sx=0∣S∣) mod (109+7)\left(\sum_{S \subseteq A, \oplus_{x \in S} x = 0} |S|\right) \bmod (10^9+7)(∑S⊆A,⊕x∈S​x=0​∣S∣)mod(109+7). Note that ⊕\oplus⊕ denotes the exclusive-or (XOR).

输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​.

* 1≤n≤1051 \leq n \leq 10^51≤n≤105
* 0≤ai≤10180 \leq a_i \leq 10^{18}0≤ai​≤1018
* The number of test cases does not exceed 100.
* The sum of n does not exceed 2×1062 \times 10^62×106.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

1
0
3
1 2 3
2
1000000000000000000 1000000000000000000

输出

复制

1
3
2

题目大意: 有n个数构成的集合,求 满足集合内元素 异或为0 的所有子集的大小.

题目思路:我们可以根据集合之间有互异性,只要一个元素在这个集合中 ,他就会出现 一次,就有一次的贡献,所以我们可以算每个数对于答案的贡献 ,首先我们求出 n个数的线性基,假设其大小为r,因为这n个元素的线性基,线性基有性质:基内的的数可以表示整个集合S中的任意数,所以有a^b=c  所以  a^b^c=0,也就是说对于 基外任何一个数,基内都会有种选择使得 a^b^c=0,所以基外任何一个数都可以与其余的 n-r-1个数产生集合合并,而且这个集合中的毎一个数都可以找到 类似于a^b,所以每一个元素的贡献就是 2^(n-r-1),n-r个元素所以有 ans+=(n-r)*(2^(n-r-1)).

考虑基内的数,如果基内的数可以由其余的n-1个数表示出来,说明还存在一个线性基,我们知道 n个元素线性基大小是一定的,所以我们只需要判断这个数会不会对答案产生贡献,如果 这个数可以放到n-1的线性基中,说明不可以,如果不可以放到 就说明存在一种组合使得 a^b^c=0,所以我们只需要求出 其余n-1个数的线性基然后判断能否放进去即可,如果能放进去说明有贡献,否则就不能.

在判断基内的数的时候,可以先把r个放进去然后,copy一个数组复制第二个线性基,然后开始n^2遍历

最后得出AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const ll INF=1e9+5;
const int maxn=1e5+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
ll x[101];
ll x1[101];
ll x2[101];
ll num[maxn];
ll num1[maxn];
ll num2[maxn];
ll sum[maxn];
bool build_judge(ll a,ll s[])//判断X线性基
{
    for(int i=62;i>=0;i--)
    {
        if((1LL<<i)&a)
        {
            if(s[i+1])
                a^=s[i+1];
            else
            {
                s[i+1]=a;
                break;
            }
        }
    }
    return a>0;
}
int main()
{
    sum[0]=1;
    for(int i=1;i<maxn;i++) sum[i]=(sum[i-1]*2)%mod;
    while(~scanf("%llu",&n))
    {
        for(int i=0;i<=60;i++) x[i]=x1[i]=0;
        ll ans=0,cot1=0,cot2=0;
        for(int i=1;i<=n;i++)
            scanf("%llu",&num[i]);
        for(int i=1;i<=n;i++)
        {
            if(build_judge(num[i],x))num1[++cot1]=num[i];
            else num2[++cot2]=num[i];
        }
        if(cot1==n) {printf("0\n");continue;}
        ans=(ans+(n-cot1)*sum[n-cot1-1])%mod;
        for(int i=1;i<=cot2;i++) build_judge(num2[i],x1);
        for(int i=1;i<=cot1;i++)
        {
            for(int k=0;k<=62;k++) x2[k]=x1[k];
            for(int k=1;k<=cot1;k++)
            {
                if(i==k) continue;
                build_judge(num1[k],x2);
            }
            if(!build_judge(num1[i],x2))
                ans=(ans+sum[n-cot1-1])%mod;
        }
        printf("%llu\n",ans);
    }
    return 0;
}

继续加油!!!