题解：CF2043F Nim

提供一种截然不同的思路。

题目等价于求区间内保留最少的数（至少一个），且所有数异或和为零的的方案数。

考虑一种朴素的 dp 思路：设

f_{i,j,s}

表示前

i

个数中保留了

j

个数，并且保留的数异或为

s

的方案数。转移的话只要考虑当前的数选不选就好了，单次转移的复杂度为

\mathcal O(64n)

。

选择了一个数，相当于把这个数放入线性基当中。考虑线性基的过程，当一个数不能被放入，那么就意味着已经能使异或和为零了；否则放入

6

轮之后，线性基就已经满了，那么下一个数就能使异或和为零。也就是说，我们只要考虑最多选

7

个数的情况就行，那么转移的复杂度变成了

\mathcal O(64\times 7)

。

总不可能每次询问都从

l

到

r

跑一次 dp，于是我们就自然想到要维护一个数据结构。再此之前，我们还需要快速合并两个 dp 数组。由于他是一维异或，另一维求和，所以不难想到用类似于子集卷积的方法来快速合并，复杂度为

\mathcal O(64\times7\times7)

。

但是我们发现这个合并的复杂度是高于转移复杂度的，所以我们要使得这种合并的操作尽可能的少。所以可以考虑用一种类似于点分治的方法，把每个询问打到最短的包含整个询问的区间，然后每个区间维护分别从中间往左和往右的 dp 数组。这样每次询问合并一次就行了。

为了省空间可以离线。最终的复杂度就是

\mathcal O(64\times 7n\log n+64\times7\times7 q)

。

注意一些小细节，就比如可能方案数刚好被模数整除之类的。

CPP

#include<iostream>
#include<cstdio>
#include<vector>
#define mod 998244353
#define inv2 499122177
using namespace std;
int n,q;
int a[100005];
struct sth{
	int l,r;
}p[100005];
int ans[100005][2];
int f[50005][1<<6][8],g[50005][1<<6][8];
int vf[50005][1<<6][8],vg[50005][1<<6][8];
vector<int>b[400005];
int f1[8][1<<6],f2[8][1<<6],f3[8][1<<6];
int g1[8][1<<6],g2[8][1<<6],g3[8][1<<6];
inline int add(int x,int y){
	if((x+=y)>=mod) x-=mod;
	return x;
}
inline int sub(int x,int y){
	if((x-=y)<0) x+=mod;
	return x;
}
void ins(int k,int l,int r,int L,int R,int id){
	if(r<L||R<l||L>R) return;
	int mid=l+r>>1;
	if(L<=mid+1&&mid<=R){
		b[k].push_back(id);
		return;
	}
	ins(k<<1,l,mid,L,R,id);
	ins(k<<1|1,mid+1,r,L,R,id);
	return;
}
void FWT(int *f){
	int x,y;
	for(int i=1;i<64;i<<=1){
		for(int j=0;j<64;j+=(i<<1)){
			for(int k=j;k<i+j;k+=1){
				x=f[k]; y=f[k+i];
				f[k]=add(x,y);
				f[k+i]=sub(x,y);
			}
		}
	}
	return;
}
void IFWT(int *f){
	int x,y;
	for(int i=1;i<64;i<<=1){
		for(int j=0;j<64;j+=(i<<1)){
			for(int k=j;k<i+j;k+=1){
				x=f[k]; y=f[k+i];
				f[k]=1ll*add(x,y)*inv2%mod;
				f[k+i]=1ll*sub(x,y)*inv2%mod;
			}
		}
	}
	return;
}
void work(int k,int l,int r){
	int t=b[k].size();
	int mid=l+r>>1;
	if(t){
		f[0][0][0]=g[0][0][0]=1;
		vf[0][0][0]=vg[0][0][0]=1;
		for(int i=mid;i>=l;i-=1){
			int x=mid-i+1;
			for(int s=0;s<64;s+=1){
				for(int j=0;j<8;j+=1){
					f[x][s][j]=f[x-1][s][j];
					vf[x][s][j]=vf[x-1][s][j];
				}
			}
			for(int s=0;s<64;s+=1){
				for(int j=1;j<8;j+=1){
					f[x][s][j]=add(f[x][s][j],f[x-1][s^a[i]][j-1]);
					vf[x][s][j]|=vf[x-1][s^a[i]][j-1];
				}
			}
		}
		for(int i=mid+1;i<=r;i+=1){
			int x=i-mid;
			for(int s=0;s<64;s+=1){
				for(int j=0;j<8;j+=1){
					g[x][s][j]=g[x-1][s][j];
					vg[x][s][j]=vg[x-1][s][j];
				}
			}
			for(int s=0;s<64;s+=1){
				for(int j=1;j<8;j+=1){
					g[x][s][j]=add(g[x][s][j],g[x-1][s^a[i]][j-1]);
					vg[x][s][j]|=vg[x-1][s^a[i]][j-1];
				}
			}
		}
		for(int i=0;i<t;i+=1){
			int x=b[k][i],L=mid-p[x].l+1,R=p[x].r-mid;
			for(int s=0;s<64;s+=1){
				for(int j=0;j<8;j+=1){
					f1[j][s]=f[L][s][j];
					f2[j][s]=g[R][s][j];
					g1[j][s]=vf[L][s][j];
					g2[j][s]=vg[R][s][j];
					f3[j][s]=g3[j][s]=0;
				}
			}
			for(int j=0;j<8;j+=1){
				FWT(f1[j]); FWT(f2[j]); FWT(g1[j]); FWT(g2[j]);
			}
			for(int i1=0;i1<8;i1+=1){
				for(int i2=0;i1+i2<8;i2+=1){
					if(!i1&&!i2) continue;
					for(int s=0;s<64;s+=1){
						f3[i1+i2][s]=add(f3[i1+i2][s],1ll*f1[i1][s]*f2[i2][s]%mod);
						g3[i1+i2][s]=add(g3[i1+i2][s],1ll*g1[i1][s]*g2[i2][s]%mod);
					}
				}
			}
			ans[x][0]=-1;
			for(int j=1;j<8;j+=1){
				IFWT(f3[j]); IFWT(g3[j]);
				if(f3[j][0]||g3[j][0]){
					ans[x][0]=(p[x].r-p[x].l+1-j);
					ans[x][1]=f3[j][0]; break;
				}
			}
		}
	}
	if(l==r) return;
	work(k<<1,l,mid); work(k<<1|1,mid+1,r);
	return;
}
void solve(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i+=1) scanf("%d",&a[i]);
	for(int i=1;i<=q;i+=1){
		scanf("%d%d",&p[i].l,&p[i].r);
		ins(1,1,n,p[i].l,p[i].r,i);
	}
	work(1,1,n);
	for(int i=1;i<=q;i+=1){
		if(~ans[i][0]) printf("%d %d\n",ans[i][0],ans[i][1]);
		else printf("-1\n");
	}
	return;
}
int main(){
	solve();
	return 0;
}

Thanks~

文章操作

相关推荐

评论

题解：CF2043F Nim