令$f_{i}$（一个集合）表示当第$i$步开始时第0方必胜当且仅当$x\in f_{i}$，初始$f_{n+1}=\{0\}$
当$p_{i}=0$时，$f_{i}=\{x|x\in f_{i+1}或(x\oplus a_{i})\in f_{i+1}\}$；当$p_{i}=1$，$f_{i}=\{x|x\in f_{i+1}且(x\oplus a_{i})\in f_{i+1}\}$
归纳$f_{i}$具有以下性质：若$x,y\in f_{i}$，则$(x\oplus y)\in f_{i}$，如果只有$p_{i}=0$显然满足此性质，考虑当$p_{i}=1$时，对$a_{i}$是否存在于$f_{i+1}$中分类讨论：
1.若$a_{i}\in f_{i+1}$，根据此性质，则有$f_{i}=f_{i+1}$
2.若$a_{i}\notin f_{i+1}$，同样根据此性质，若$(x\oplus a_{i})\in f_{i+1}$，则$a_{i}\in f_{i+1}$，与假设矛盾，因此$f_{i}=\emptyset$
这个性质类似于线性基，因此用线性基来维护$f_{i}$即可，时间复杂度为$o(tn\log_{2}a_{i})$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 205 4 #define ll long long 5 int t,n,ans; 6 ll a[N],w[N]; 7 char s[N]; 8 void add(ll k){ 9 for(int i=59;i>=0;i--) 10 if (k&(1LL<<i)){ 11 if (!w[i])w[i]=k; 12 k^=w[i]; 13 } 14 } 15 bool check(ll k){ 16 for(int i=59;i>=0;i--) 17 if (k&(1LL<<i)){ 18 if (!w[i])return 0; 19 k^=w[i]; 20 } 21 return 1; 22 } 23 int main(){ 24 scanf("%d",&t); 25 while (t--){ 26 scanf("%d",&n); 27 for(int i=1;i<=n;i++)scanf("%lld",&a[i]); 28 scanf("%s",s+1); 29 memset(w,0,sizeof(w)); 30 ans=0; 31 for(int i=n;i;i--) 32 if (s[i]==‘0‘)add(a[i]); 33 else{ 34 if (!check(a[i])){ 35 ans=1; 36 break; 37 } 38 } 39 printf("%d\n",ans); 40 } 41 }
原文：https://www.cnblogs.com/PYWBKTDA/p/14151254.html
