959F - Mahmoud and Ehab and yet another xor task xor+dp+离线
题意
给出 n个值和q个询问，询问l,x,表示前l个数字子序列的异或和为x的子序列有多少，其中空序列的异或和为0,一个数字的子序列的异或和是它本身
思路
维护一个集合，记录已经存在在里面的数。
首先我们证明
1.当x在这个集合，y在这个集合的时候\(x\bigoplus y\)也在这个集合里面，因为
\(x=a\bigoplus b\)
\(y=c\bigoplus d\)
所有\(x\bigoplus y==a\bigoplus b \bigoplus c\bigoplus d\)所一定存在在集合中
2.当x在这个集合中y不在这个集合中的时候，\(x\bigoplus y\)不在这个集合中
假设\(x\bigoplus y\)在这个集合中 那么\((x\bigoplus y)\bigoplus x\)也在这个集合中也就是y在这个集合中与题设矛盾
设dp[i][x]表示前i个异或和为x的数量，则有\(dp[i][x]=dp[i-1][x]+dp[i-1][x\bigoplus a[i]]\)
我们用数学归纳法证明 假设对i-1的都成立。
设dp[i-1][x]=j
假设x和a[i]都在set集合中
那么由以上的证明可以知道\(x\bigoplus a[i]\)也在集合中因此,\(dp[i-1][x]=j\)并且\(dp[i-1][x\bigoplus a[i]]=j\)因为dp[i-1][x]的数量已经知道是j了，而a[i]又在集合中，所以每个异或和为x的子序列再异或一个a[i]就变成了\(dp[i-1][x\bigoplus a[i]]\)所以两者数量都为j。
假设a[i]不在集合中
对于x有三种情况
如果x在集合中，由以上证明\(x\bigoplus a[i]\)不在集合中\(dp[i][x]=dp[i-1][x]+dp[i-1][x\bigoplus a[i]]=j+0=0\)
如果x要在这一步被添加到set中，即\(x\bigoplus a[i]\)在集合中，那么有\(dp[i][x]=dp[i-1][x]+dp[i-1][x\bigoplus a[i]]=0+j=j\)
如果不属于上面三种情况，那么\(dp[i][x]=dp[i-1][x]+dp[i-1][x\bigoplus a[i]]=0+0=0\)
得证
ps:for(auto:s)s.pb()在有的版本不会死循环，但以后要注意，避免傻逼错误
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
typedef long long ll;
using namespace std;
const ll maxn=1e5+7;;
const int mod=1e9+7;
int vis[(1<<20)+5];
vector<int>s;
int ans[maxn];
int a[maxn];
vector<pair<int,int> >v[(1<<20)+5];
int main(){
int n,q;
int x,y;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
v[x].pb({y,i});
}
ll tmp=1;
s.pb(0);
vis[0]=1;
for(int i=1;i<=n;i++){
//cout<<i<<endl;
if(vis[a[i]]){
tmp=tmp*2%mod;
// cout<<111<<endl;
}
else {
/*for(auto p:s){
vis[p^a[i]]=1;
s.pb(p^a[i]);
}*/
int zz=s.size();
for(int j=0;j<zz;j++){
// cout<<s.size()<<" "<<j<<endl;
vis[s[j]^a[i]]=1;
s.pb(s[j]^a[i]);
}
}
// cout<<333<<endl;
/*for(auto&p:v[i]){
ans[p.S]=tmp*vis[p.F];
}*/
for(int j=0;j<v[i].size();j++){
ans[v[i][j].S]=tmp*vis[v[i][j].F];
}
}
for(int i=1;i<=q;i++){
printf("%d\n",ans[i]);
}
return 0;
}