120561H_牛客博客

https://ac.nowcoder.com/acm/contest/120561/H

先给一个结论：对一个确定数列（ $a_i\in [0,2^{31}]$ ），以 $a_i$ 开头/结尾的前缀/后缀或和最多只有 $32$ 个。

那么就很好做了：定义 $f_{i,j}$ 为以 $i$ 结尾，后缀或和为 $j$ 的符合题目的数量。显然有转移：

$f_{i,a_i}=\sum_{j=1}^{+\infty}f_{i-1,j}$

令数列 $b_j$ 储存当前 $i-1$ 下以 $i-1$ 为结尾的后缀或和。

则有：

$f_{i,a_i|b_j}+=f_{i-1,b_j}\times((a_i|b_j)==(a_i+b_j))$

由于一个 $i$ 有的 $b$ 最多只有 $32$ 个，可以用 $map$ 储存 $b_i$ 。时间复杂度 $O(nlogV)$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
long long f[200100][110],n,a[1000100];

const long long p=998244353;
long long read(){
	char ch=getchar();long long x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
void work(){
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=33;j++){
			f[i][j]=0;
		}
	}
	n=read();
	for(long long i=1;i<=n;i++) a[i]=read();
	long long b[35],tot=0,c[35],cnt=0,ans=0;
	map<long long,int>mpb,mpc;
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	mpb[a[1]]=++tot;
	b[tot]=a[1];
	f[1][mpb[a[1]]]=1;
	for(long long i=2;i<=n;i++){
		cnt=0;mpc.clear();
		c[++cnt]=a[i];mpc[a[i]]=cnt;
		for(long long j=1;j<=tot;j++){
			f[i][mpc[a[i]]]+=f[i-1][mpb[b[j]]];
			if(f[i][mpc[a[i]]]>p) f[i][mpc[a[i]]]-=p;
			if((b[j]|a[i])==(b[j]+a[i])){
				if(!mpc[b[j]|a[i]]){
					mpc[b[j]|a[i]]=++cnt;
					c[cnt]=b[j]|a[i];	
				}	
				f[i][mpc[b[j]|a[i]]]+=f[i-1][mpb[b[j]]];
				if(f[i][mpc[b[j]|a[i]]]>p) f[i][mpc[b[j]|a[i]]]-=p;	
			}	
		}
		mpb.clear();
		tot=0;
		for(long long j=1;j<=cnt;j++){
			b[++tot]=c[j];
			mpb[b[tot]]=tot;
		}
	}
	for(long long i=1;i<=tot;i++){
		ans+=f[n][i];
		if(ans>p) ans-=p;
	}
	printf("%lld\n",ans);
}
int main(){
	int t=read();
	while(t--){
		work();
	}
	return 0;
}