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

本是古典何须时尚 2021-11-13 19:00 306阅读 0赞

[https://ac.nowcoder.com/acm/contest/881/H][https_ac.nowcoder.com_acm_contest_881_H]

--------------------

### 题意： ###

给定n个整数，求其中异或和为 \\(0\\) 的子集的大小的和。

### 题解思路： ###

首先转化为每个可以通过异或表示 \\(0\\) 的数贡献它参与的子集数。

思考的过程分两步。一开始不管三七二十一先对 \\(n\\) 个整数求一次线性基 \\(B\_1\\) ，记其秩为 \\(r\\) 。

### 第一步： ###

先考虑线性基 \\(B\_1\\) 外的数（假如有的话）产生的贡献。枚举每一个数，记这个数为 \\(x\\) ，除去这个数，线性基 \\(B\_1\\) 外还有 \\(n-r-1\\) 个数，他们可以自由组合出 \\(2^\{n-r-1\}\\) 种子集，加上 \\(x\\) 本身之后，必定能被线性基 \\(B\_1\\) 表示，故这些子集都会使得 \\(x\\) 发生贡献。这样的 \\(x\\) 共有 \\(n-r\\) 个。

### 第二步： ###

再考虑线性基 \\(B\_1\\) 中的数产生的贡献。枚举每一个数，记这个数为 \\(x\\) ，这个数产生的贡献来源于他在第一步中被使用的次数。那怎么判断这个数被使用了多少次呢？把除去这个数 \\(x\\) 的 \\(n-1\\) 个数求出线性基 \\(B\_3\\) 。假如 \\(x\\) 能被线性基 \\(B\_3\\) 表示，此时 \\(B\_3\\) 的秩必定为 \\(r\\) 。选中\\(x\\)之后，再从其他的 \\(n-r-1\\) 个数自由组合出子集，再从 \\(B\_3\\)中选出对应的数配成 \\(0\\) 。否则这个 \\(x\\) 没有用。

### 第三步： ###

最后是快速得到 \\(B\_3\\) 的办法，注意到 \\(B\_3\\) 必定先通过除去 \\(B\_1\\) 的 \\(n-r\\) 个数构造，可以把 \\(n-r\\) 先构造出 \\(B\_2\\) ，然后再插入 \\(B\_1\\) 内除x的 \\(r-1\\) 个数构成。

注意MN不能取64否则会爆掉ll。

--------------------

qls说是hdu5544 [http://acm.hdu.edu.cn/showproblem.php?pid=5544][http_acm.hdu.edu.cn_showproblem.php_pid_5544]

题意：给定n个整数，求其中异或和为0的子集的大小的和。

题解思路：

首先转化为每个可以通过异或表示0的数贡献它参与的子集数。

对n个数进行一次消元，得到一组大小为\\(r\\)的线性基B1。

那么剩下的\\(n-r\\)个满足以下的规律：

设现在要计算的元素为X1，其他\\(n-r-1\\)个元素任意组合，总能得到一个整数，再加入X1也是一个整数，这个整数能被线性基B1表示，则这个X1可以对他们贡献总计\\(2^\{n-r-1\}\\)个次。

接下来算线性基B1里的数的贡献。

再对这\\(n-r\\)个数进行一次消元， 得到另一组线性基B2。枚举B1的一个线性基X2，对其他的r-1+B2个数消元，得到某个线性基B3。

csl：你必须钦定一个数必须选，如果这个数在线性基外面那没事，在里面你就得搞事情了。

意思是：这个数在线性基外面说明没有集合需要它的参与就可以自己组成异或和为0的。要是在线性基里面就说明存在这个数可以对某些集合产生贡献。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MN=63; const int mod=1000000007; ll num[100005]; struct LinearBase { ll base[MN]; bool flag;//该线性基能否表示0 int cnt; void Copy(LinearBase b) { cnt=b.cnt; flag=b.flag; memcpy(base,b.base,sizeof(base)); } void Clear() { cnt=0; flag=false; memset(base,0,sizeof( base)); } //尝试向线性基中插入一个值 void Insert(ll x) { for(int i=MN; ~i; i--) if(x&(1ll<<i)) if(!base[i]) { base[i]=x; cnt++; return; } else x^=base[i]; flag=true; } //判断该线性基能否表示x bool Check(ll x) { for(int i=MN; ~i; i--) if(x&(1ll<<i)) { if(!base[i]) return false; else x^=base[i]; } return true; } } B1,B2,B3; ll qpow(ll x,int n) { ll res=1; while(n) { if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } ll ans,p2; vector<int>B1ID; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); //freopen("Yinku.out", "w", stdout); #endif // Yinku int n; while(~scanf("%d", &n)) { for(int i=1; i<=n; i++) { scanf("%lld",&num[i]); } B1.Clear(); B2.Clear(); B1ID.clear(); for(int i=1; i<=n; i++) { if(B1.Check(num[i])) { B2.Insert(num[i]); } else { B1.Insert(num[i]); B1ID.push_back(i); } } ans=0; if(n!=B1.cnt) { p2=qpow(2,n-B1.cnt-1); ans+=p2*(n-B1.cnt)%mod; } for(ll i:B1ID) { B3.Copy(B2); for(ll j:B1ID) { if(i!=j) { B3.Insert(num[j]); } } if(B3.Check(num[i])) { //num[i]能被其他数表示 ans=(ans+p2)%mod; } } printf("%lld\n", ans); } }

--------------------

转载于:https://www.cnblogs.com/Yinku/p/11212303.html

[https_ac.nowcoder.com_acm_contest_881_H]: https://ac.nowcoder.com/acm/contest/881/H
[http_acm.hdu.edu.cn_showproblem.php_pid_5544]: http://acm.hdu.edu.cn/showproblem.php?pid=5544