P7620 CF1431J Zero-XOR Array（枚举 +dp）
panyf
·
·
题解
记 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_2$ 表示当前异或和为 $0$，且存在数满足状态 3。
$f_3$ 表示当前异或和为 $1$，且存在数满足状态 3。
具体转移方程见代码，设 $s$ 的第 $k$ 位为 $x$，则 $f_{2|x}$ 即为方案数。
时间复杂度 $O(2^nnm)$。
```cpp
#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;
}
```