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;
}
05-11 22:27