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

不念不忘少年蓝@ 2021-10-23 10:13 361阅读 0赞

**题目链接：**[https://ac.nowcoder.com/acm/contest/881/H][https_ac.nowcoder.com_acm_contest_881_H]

**题目大意：**给定n个整数，求满足子集异或和为0的子集大小之和。

**解题报告：**

先把n个数分成两部分，线性基外与线性基内

1. 对n个数试着插入线性基，如果不能插入，证明它能被线性基内的数异或得到，即这个数的贡献为1，把这些不能插入线性基的数构成一个集合，考虑一个数必选，那么与它组合的方式共有$2^\{n-r-1\}$种，r为线性基内的数，减1是为了减去这个数（因为它必选），共有$（n-r）$个数，所以**线性基外的数的贡献为$(n-r)\*2^\{n-r-1\}$**

2. 对于线性基内的数，枚举每一个数，对于剩下的n-1个数建立线性基，如果它不能插入线性基，不难证明这个线性基的大小已经为r，这个数的贡献便为1，总共有temp个数，所以**线性基内的数的总贡献便为$temp\*2^\{n-r-1\}$**

**答案：$(n-r)\*2^\{n-r-1\}+temp\*2^\{n-r-1\}$**

**AC代码：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 #define numm ch-48
     3 #define pd putchar(' ')
     4 #define pn putchar('\n')
     5 #define pb push_back
     6 #define fi first
     7 #define se second
     8 #define fre1 freopen("1.txt","r",stdin)
     9 #define fre2 freopen("2.txt","w",stdout)
    10 using namespace std;
    11 template <typename T>
    12 void read(T &res) {
    13     bool flag=false;char ch;
    14     while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true);
    15     for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);
    16     flag&&(res=-res);
    17 }
    18 template <typename T>
    19 void write(T x) {
    20     if(x<0) putchar('-'),x=-x;
    21     if(x>9) write(x/10);
    22     putchar(x%10+'0');
    23 }
    24 typedef long long ll;
    25 const int maxn=1e5+7;
    26 const int N=60;
    27 const ll mod=1e9+7;
    28 struct node {
    29     int r;
    30     ll p[70];
    31     void init() {
    32         r=0;
    33         for(int i=62;~i;i--)
    34             p[i]=0;
    35     }
    36     bool ins(ll x) {
    37         for(ll i=62;~i;i--) {
    38             if(x&(1LL<<i)){
    39                 if(!p[i]) {
    40                     p[i]=x;
    41                     r++;
    42                     return true;
    43                 } else x^=p[i];
    44             }
    45         }
    46         return false;
    47     }
    48 }b1,b2,b3;
    49 vector<ll>v;
    50 ll quickpow(ll a,ll b) {
    51     ll ans=1;
    52     while(b) {
    53         if(b&1) ans=(ans*a)%mod;
    54         a=(a*a)%mod;
    55         b>>=1;
    56     }
    57     return ans;
    58 }
    59 int main()
    60 {
    61     int n;
    62     while(scanf("%d",&n)!=EOF) {
    63         b1.init();
    64         b2.init();
    65         b3.init();
    66         v.clear();
    67         for(int i=1;i<=n;i++) {
    68             ll x;
    69             read(x);
    70             if(b1.ins(x)) {     ///线性基内
    71                 v.pb(x);
    72             }
    73             else b2.ins(x);     ///线性基外
    74         }
    75         if(b1.r==n) {
    76             write(0);pn;continue;
    77         }
    78         ll ans=(n-b1.r)*quickpow(2,n-b1.r-1)%mod;///线性基外求解
    79         ll temp=0;
    80         for(int i=0;i<v.size();i++) {   ///线性基内求解
    81             b3=b2;
    82             for(int j=0;j<v.size();j++) {
    83                 if(i==j) continue;
    84                 b3.ins(v[j]);
    85             }
    86             if(b3.r==b1.r) temp++;
    87         }
    88         ans=(ans+temp*quickpow(2,n-b1.r-1))%mod;
    89         write(ans);pn;
    90     }
    91     return 0;
    92 }

代码在这里！

转载于:https://www.cnblogs.com/wuliking/p/11330675.html

[https_ac.nowcoder.com_acm_contest_881_H]: https://ac.nowcoder.com/acm/contest/881/H
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/9ea38d91ddb34be885fdf3141b81d6cf.png