2019牛客暑期多校训练营（第一场） - H XOR（线性基）

发表于 | 分类于 ，

H-XOR
给定一个集合，求它异或和为0的子集的大小总和

题意

给定$n$个数${a_i}$，求它异或和为0的子集的大小总和。

题解

考虑求集合中的每个元素对答案的贡献。

设$a$中不在线性基中的集合$S(|S|=n-|B|)$，它的任意一个子集的异或和一定可以表示为线性基中若干个数的异或和。对于某个不在线性基中的元素$a_i$，包含它的集合$S$的子集数量为$2^{n-|B|-1}$个。

对于线性基中的某个二进制位$x$，如果有一个不在线性基内的数$a_j$满足(1<<x)&a[j]==1，则表示原本为这一位基底的$a_i$可以被$a_j$替换，并构成一个新的线性基$B’$,此时视$a_i$为在线性基外的元素，其对答案的贡献为$2^{n-|B|-1}$。

最后的答案为$$ans=(n-|B|+cnt)×2^{n-|B|-1}$$，其中$cnt$表示线性基中能被替换的向量个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
typedef long long ll;

ll qp(ll a, ll n)
{
    if(n < 0) return 0;
    ll ans = 1;
    for(;n ; (a *= a) %= mod, n >>= 1) if(n & 1) (ans *= a) %= mod;
    return ans;
}

ll v;

struct LinearBasis
{
	ll d[63], o[63];   //原矩阵，对角矩阵

	void init()
	{
		for(int i = 0; i < 64; i ++) d[i] = o[i] = 0;
		v = 0;
	}

	bool ins(ll x)
	{
	    ll tmp = 0;
	    bool flag = false;
		for(int i = 62; i >= 0; i --)
		{
			if((x >> i) & 1)
			{
				if(!d[i]) d[i] = x, o[i] = tmp | (1ll << i), flag = true;
				x ^= d[i]; tmp ^= o[i];
				if(!x) break;
			}
		}
		if(!flag) v |= tmp;
		return flag;
	}
}L;

int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        L.init();
        ll x, ans = 0, cnt = 0;
        for(int i = 0; i < n; i ++)
        {
            scanf("%lld", &x);
            if(!L.ins(x)) ans ++;
        }
        for(int i = 0; i < 63; i ++)
        {
            if(L.d[i]) cnt ++;
            if((1ll << i) & v) ans ++;
        }
        printf("%lld\n", ans * qp(2, n - cnt - 1) % mod);
    }
    return 0;
}