自动搬运

查看原文

来自洛谷，原作者为

	panyf **

搬运于2025-08-24 22:31:36，当前版本为作者最后更新于2021-06-18 10:48:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

记 $s=a_1\oplus a_2\oplus...\oplus a_n$。

题意可以转化为求长度为 $n-1$ 的整数序列 $c_i$，满足 $a_i\leq c_i\leq a_{i+1}$，且 $c_1\oplus c_2\oplus...\oplus c_{n-1}=s$ 的方案数。

从高位到低位枚举。设当前枚举到第 $k$ 位（最低位为第 $0$ 位），$c_i$ 一定属于以下状态之一：

1.第 $k+1$ 位到第 $m-1$ 位的前缀和 $a_{i}$ 的前缀相同；

2.前缀和 $a_{i+1}$ 相同且不和 $a_{i}$ 相同；

3.前缀和 $a_{i+1}$ 及 $a_{i}$ 都不同。

发现一个性质：

某一时刻，若存在一个 $c_i$ 满足状态 3，记 $l_j$ 为确定了前缀后 $c_j$ 可以取到的最小值，$r_j$ 为最大值，则方案数为 $\Pi_{j\neq i}(r_j-l_j+1)$。

原因：任意选择除 $i$ 以外的 $c_j$，因为 $c_i$ 满足状态 3，所以后 $k$ 位的 $2^k$ 种情况都可以取到，所以其中有且仅有一种情况可以使异或和等于 $s$。

考虑枚举 $k$，表示在第 $k$ 位时第一次出现一个数满足状态 3。

暴力枚举第 $k+1$ 位时所有数的状态，因为只存在前两种，所以至多 $2^{n-1}$ 种状态。

先判断状态是否合法。

若合法，考虑 dp。

记 $f_0$ 表示当前异或和为 $0$，且不存在数满足状态 3。

$f_1$ 表示当前异或和为 $1$，且不存在数满足状态 3。

$f_2$ 表示当前异或和为 $0$，且存在数满足状态 3。

$f_3$ 表示当前异或和为 $1$，且存在数满足状态 3。

具体转移方程见代码，设 $s$ 的第 $k$ 位为 $x$，则 $f_{2|x}$ 即为方案数。

时间复杂度 $O(2^nnm)$。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int P=998244353;
ll a[19],b[19],s;
int n,m,p[19],f[4],g[4];
bool chk(int o,int k){//判断第k位状态o是否合法
	ll w=0;
	for(int i=0;i<n;++i){
		if(o>>i&1){
			if(p[i]<k)return 0;
			w^=b[i];
		}else w^=a[i];
	}
	return(w>>k)==(s>>k);
}
void wk(int x,ll v){v%=P;for(int i=0;i<4;++i)g[i^x]=(g[i^x]+f[i]*v)%P;}//非状态3的转移
void wk2(int x,ll v){v%=P,g[2^x]=(g[2^x]+f[2]*v+f[0])%P,g[3^x]=(g[3^x]+f[3]*v+f[1])%P;}//状态3的转移
int main(){
	int o,ans=0,i,j,k;
	for(scanf("%d%d",&n,&m),--m,i=0;i<n;++i)scanf("%lld",a+i),s^=a[i];
	for(i=0,--n;i<n;++i)for(b[i]=a[i+1],j=m,p[i]=-1;~j;--j)if((a[i]>>j&1)!=(b[i]>>j&1)){p[i]=j;break;}//p[i]表示最大的k满足a[i]和a[i+1]的第k位不同
	for(o=1<<n,i=0;i<o;++i)if(chk(i,0))++ans;//处理不存在状态3的情况
	for(k=0;k<m;++k)for(j=0;j<o;++j)if(chk(j,k+1)){
		f[0]=1,f[1]=f[2]=f[3]=0;
		for(i=0;i<n;memcpy(f,g,16),memset(g,0,16),++i){
			if(p[i]<k)wk(a[i]>>k&1,b[i]-a[i]+1);
			else if(p[i]==k)wk(0,(b[i]>>k<<k)-a[i]),wk(1,b[i]-(b[i]>>k<<k)+1);
			else if(j>>i&1){
				if(b[i]>>k&1)wk(1,b[i]-(b[i]>>k<<k)+1),wk2(0,1ll<<k);
				else wk(0,b[i]-(b[i]>>k<<k)+1);
			}else{
				if(a[i]>>k&1)wk(1,(1ll<<k)-a[i]+(a[i]>>k<<k));
				else wk(0,(1ll<<k)-a[i]+(a[i]>>k<<k)),wk2(1,1ll<<k);
			}
		}
		ans=(ans+f[2|(s>>k&1)])%P;
	}
	printf("%d",ans);
	return 0;
}