題干：

鏈接：https://ac.nowcoder.com/acm/contest/881/H
來源：牛客網(wǎng)
?

Bobo has a set A of n integers a1,a2,…,ana1,a2,…,an.
He wants to know the sum of sizes for all subsets of A whose xor sum is zero modulo (109+7)(109+7).
Formally, find (∑S?A,⊕x∈Sx=0|S|)mod(109+7)(∑S?A,⊕x∈Sx=0|S|)mod(109+7). Note that ⊕⊕ 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,…,ana1,a2,…,an.* 1≤n≤1051≤n≤105 * 0≤ai≤10180≤ai≤1018 * The number of test cases does not exceed 100. * The sum of n does not exceed 2×1062×106.

輸出描述:

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

示例1

輸入

復(fù)制

1 0 3 1 2 3 2 1000000000000000000 1000000000000000000

輸出

復(fù)制

1 3 2

題目大意：

給你n個(gè)數(shù)字，然后讓你求所有滿足 異或和為0的子集 的大小之和。

解題報(bào)告：

根據(jù)期望的線性性(Orz)，轉(zhuǎn)化一下題意：相當(dāng)于求每個(gè)數(shù)出現(xiàn)在子集中的次數(shù)之和。

那么如何求每個(gè)的合法出現(xiàn)次數(shù)呢？對于每個(gè)數(shù)x的出現(xiàn)次數(shù)，也就是這個(gè)數(shù)x必選的情況下，有多少種選擇方案可以讓剩余n-1個(gè)數(shù)湊出x來。然后就可以

先對n個(gè)數(shù)求線性基b1，設(shè)線性基大小為r，可以分別計(jì)算線性基內(nèi)數(shù)的貢獻(xiàn)和線性基外數(shù)的貢獻(xiàn)

1.線性基外：共n-r個(gè)數(shù)，枚舉每個(gè)數(shù)，讓他必選，將線性基外剩余的個(gè)數(shù)任意排列（也可不選），則共有?種方案，每種方案再異或x的結(jié)果，能被剛剛求出的那組線性基唯一的異或出來，所以每個(gè)數(shù)的貢獻(xiàn)為：。又因?yàn)橐还灿衝-r個(gè)數(shù)，所以線性基外的數(shù)的貢獻(xiàn)為：

2.線性基內(nèi)：依舊是枚舉每個(gè)數(shù)x（注意枚舉的x是a數(shù)組中的數(shù)而不是b1中的數(shù)），求出剩余n-1個(gè)數(shù)湊出x的方案數(shù)，做法是這樣的：將所有剩余的n-1個(gè)數(shù)再求一次線性基，設(shè)為b2，分兩種情況：

(1) x不能被b2異或出。那么顯然x不能在任意一個(gè)集合中出現(xiàn)，x的貢獻(xiàn)為0。

(2) x可以被b2異或出。此時(shí)b2的大小必定也為r，因?yàn)閎2已經(jīng)能表示所有n個(gè)數(shù)了。那么在除去x和b2的情況下，剩余n-r-1個(gè)數(shù)顯然也是任意排列，x貢獻(xiàn)為?。

對于在線性基內(nèi)的方案統(tǒng)計(jì)時(shí)，還有另一種理解：因?yàn)檫@個(gè)數(shù)x在線性基內(nèi)，也就是說他代表了二進(jìn)制中的一個(gè)Bit位在線性基中的存在，那么我們要湊出這個(gè)x的話（注意x依舊是原數(shù)，而不是線性基內(nèi)的數(shù)字），就必須要找一個(gè)可以代表這個(gè)Bit位的數(shù)字來替代他，也就是：用除去x的剩余n-1個(gè)數(shù)，重構(gòu)一組線性基后，如果基的大小仍為b1.r，則說明x在原基b1中不是必須的，可以被替代，此時(shí)也才說明x對答案做出了貢獻(xiàn)，不然的話只有x能代表這個(gè)Bit，那他代表給誰看？和誰去異或成0？所以對答案沒有任何貢獻(xiàn)。所以寫代碼最后一部分的時(shí)候，既可以這樣寫：if(b3.r == b1.r) 也可以這樣寫：if(b3.ins(a[i])==0)也就是說如果插不進(jìn)去a[i]了，就代表他對答案做出了貢獻(xiàn)，因?yàn)樾禄梢詼惓鏊袛?shù)字。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; const ll mod = 1e9 + 7; int n,top; ll a[MAX],ans,tmp,b[MAX]; struct Node {ll Base[66];int r;void init() {memset(Base,0,sizeof Base);r=0;}bool ins(ll x) {for(int i = 62; i>=0; i--) {if(x & (1LL<<i)) {if(Base[i] == 0) {Base[i] = x;r++;return 1;}else x ^= Base[i];}if(x == 0) return 0;}return 0;} } b1,b2,b3; ll qpow(ll a,ll k) {ll res = 1;while(k) {if(k&1) {res = (res * a) % mod;}k>>=1;a = (a * a)%mod;}return res; } int main() {while(~scanf("%d",&n)) {ans = tmp = 0;b1.init();b2.init();top=0;for(int i = 1; i<=n; i++) scanf("%lld",a+i);for(int i = 1; i<=n; i++) {if(b1.ins(a[i])) b[++top] = a[i];else b2.ins(a[i]);}if(n == b1.r) {printf("0\n");continue;}ans = (n-b1.r) * qpow(2,n - b1.r - 1);for(int i = 1; i<=top; i++) {b3 = b2;for(int j = 1; j<=top; j++) {if(i == j) continue;b3.ins(b[j]);}if(b3.r == b1.r) tmp++;}ans = ans + tmp*qpow(2,n - b1.r - 1);printf("%lld\n",ans%mod);} return 0 ; }

AC代碼2：（咖啡雞的代碼，也不知道是維護(hù)了個(gè)啥）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+3; const ll M=1000000007; ll v; struct base{ll r[64],o[64];bool ins(ll x){bool flag=0;ll tmp=0;for (int i=62;i>=0;i--)if (x>>i){if (!r[i]) o[i]=tmp|(1ll<<i),r[i]=x,flag=1;x^=r[i]; tmp^=o[i];if (!x) break;}if (!flag){v|=tmp;}return flag;}void clear(){for (int i=0;i<64;i++) r[i]=0,o[i]=0;} }f; ll pow_(ll x,ll y){ll ret=1;while (y){if (y&1) ret=ret*x%M;x=x*x%M; y>>=1;}return ret; } int n,w; ll a[maxn],ans;int main(){while (scanf("%d",&n)==1){for (int i=1;i<=n;i++) scanf("%lld",&a[i]);for (int i=0;i<64;i++) v=0; f.clear(); ans=w=0;for (int i=1;i<=n;i++){ans+=!f.ins(a[i]);}for (int i=0;i<64;i++) {if (v&(1ll<<i)) ++ans;if (f.r[i]) ++w;}cout << ans*pow_(2ll,n-1-w)%M << endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【2019牛客暑期多校训练营（第一场） - H】XOR（线性基，期望的线性性）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。