526互联

Codeforces 1896H2 - Cyclic Hamming (Hard Version)

发布时间 2024-01-02 20:36:44作者: tzc_wk

非常厉害的一道计数题。从去年做到了今年。给出题人点个赞！

首先乍一看这个 \(2^k\) 的这个条件给的非常奇怪，看上去有一些奇妙的玄机。因此先尝试从这里入手找些突破口。考虑 \(a\) 和 \(b\) 中任意两个 \(1\)，会有恰好一个 \(b\) 的循环移位满足这两个 \(1\) 刚好能匹配上，而题目要求 \(a,b\) 中 \(1\) 的个数都是 \(2^k\)，这意味着总共有 \(2^{2k}\) 对这样的 \(1\)，因此 \(\sum\limits_{b'\text{是}a\text{的循环移位}} f(a,b')=2^{2k}\)，而总共有 \(2^{k+1}\) 个 \(b'\)，这意味着如果有 \(f(a,b')<2^{k-1}\)，就必然有 \(f(a,b')>2^{k-1}\)。换句话说题目的条件成立当且仅当所有 \(f(a,b')\) 都等于 \(2^k\)。

分析到这一步还不足以我们解决问题，因为 hamming distance 这个东西如果硬要 DP 什么的话没办法在状态里只塞 \(\text{poly}(2^k)\) 个状态实现，状态数至少得是指数级别的，不太行。还有什么好办法呢？比较考验经验的一步到了。考虑用多项式来刻画字符串匹配，更具体地，考虑差卷积，令 \(P(x)=\sum\limits_{i=0}^{2^{k+1}-1}a_ix^i,Q(x)=\sum\limits_{i=0}^{2^{k+1}-1}b_{2^{k+1}-1-i}x^i\)，那么一组 \(a,b\) 合法当且仅当 \(P(x)Q(x)=2^{k-1}(\sum\limits_{i=0}^{2^{k+1}-1}x^i)\)，其中乘法定义为长度为 \(2^{k+1}\) 的循环卷积。这个结论看起来还是不是很好维护，我们尝试再给它卷上一个 \(x-1\)，这样多项式变成了 \(0\)，这样条件又可以写作 \(P(x)Q(x)(x-1)=0\)。

循环卷积很容易与 FFT 联系起来。显然你对 \(x-1\) 这个多项式做 DFT 之后有且仅有下标为 \(0\) 的位置上值为 \(0\)，因此 \(x-1\) 这个多项式在这里的作用显然是把点乘以后的多项式的常数项变为 \(0\) 的，因此考虑 \(p_x=\sum\limits_{i=0}^{2^{k+1}-1}a_i\omega_{2^{k+1}}^x,q_x=\sum\limits_{i=0}^{2^{k+1}-1}b_{2^{k+1}-i-1}\omega_{2^{k+1}}^x\)，合法的充要条件又可以改为 \(\forall i\in[1,2^{k+1}-1]\) 要么 \(p_i=0\) 要么 \(q_i=0\)。

考虑对 \(a,b\) 做蝴蝶变换，设 \(a\) 蝴蝶变换以后的数组为 \(c\)，\(b\) 的翻转做蝴蝶变换以后的数组为 \(d\)。那么考虑 \(x=j·2^t\)（其中 \(j\) 是奇数），可以证明 \(p_x=\sum\limits_{i=0}^{2^{k-t}-1}(\sum\limits_{l=i·2^{t+1}}^{i·2^{t+1}+2^t-1}c_l-\sum\limits_{l=i·2^{t+1}+2^t}^{i·2^{t+1}+2^{t+1}-1}c_l)·\omega_{2^{k-t+1}}^i\)（直接套用 butterfly 的过程往里面带入就行了，带入到最底层 \(\omega=-1\) 的时候就是两项做差），\(q_x\) 也同理。

考虑这样一个性质：\(\forall n>0\)，\(\omega_{2^n}^0,\omega_{2^n}^1,\cdots,\omega_{2^n}^{2^{n-1}-1}\) 在 \(\mathbb{Q}\) 上线性无关。

证明：考虑数学归纳法，当 \(n=1\) 时候只有一个数 \(1\)，显然成立。假设命题对 \(n=k\) 成立，考虑 \(n=k+1\)，反证法，假设存在 \(a_0\omega_{2^{k+1}}^0+a_1\omega_{2^{k+1}}^1+\cdots+a_{2^k-1}\omega_{2^{k+1}}^{2^k-1}=0\) 且 \(\exists a_i\ne 0\)，那么我们按照下标奇偶性分成两组发现式子可以写成 \(A+B\omega_{2^{k+1}}\) 的形式，其中 \(A,B\) 是 \(\omega_{2^k}^0,\omega_{2^k}^1,\cdots,\omega_{2^k}^{2^{k-1}-1}\) 的线性组合，两边平方可以得到 \(A^2+B^2\omega_{2^k}+2AB\omega_{2^{k+1}}=0\)。因为 \(\exists a_i\ne 0\) 且命题对 \(n=k\) 成立，所以 \(A,B\) 不全为 \(0\)，这样 \(\omega_{2^{k+1}}=-\dfrac{A^2+B^2\omega_{2^k}}{2AB}\)。即 \(\omega_{2^{k+1}}\) 可以表示为 \(\omega_{2^k}^0\sim \omega_{2^k}^{2^{k-1}-1}\) 以有理数为权重的线性组合，这是不成立的，因此由数学归纳法可知命题成立。

这也就说明了，\(p_x=0\)，当且仅当对于 \(i=0\sim 2^{k-t}-1\)，都有 \(\sum\limits_{l=i·2^{t+1}}^{i·2^{t+1}+2^t-1}c_l-\sum\limits_{l=i·2^{t+1}+2^t}^{i·2^{t+1}+2^{t+1}-1}c_l=0\)。根据这个性质可以知道对于所有 lowbit 相同的 \(x\)，它们的 \(p_x\) 要么全为 \(0\) 要么全不为 \(0\)。对于 lowbit 为 \(2^t\) 的 \(x\)，它们的 \(p_x\) 全为 \(0\) 的充要条件是，将序列 \(c\) 的划分成 \(0\sim 2^{t+1},2^{t+1}\sim 2·2^{t+1},2·2^{t+1}\sim 3·2^{t+1}\) 这 \(2^{k-t}\) 段，每一段都满足，前 \(2^{t}\) 位里 \(1\) 的个数与后 \(2^{t}\) 位里 \(1\) 的个数相同。

这样我们设 \(f_S\) 表示，恰有 \(S\) 里的 \(t\) 满足，所有 lowbit 等于 \(2^t\) 的 \(x\) 有 \(p_x=0\) 的方案数。\(g_S\) 则是相对于 \(q\) 而言的，这样答案可以表示为 \(\sum\limits_{S\cup T=U}f_Sg_T\)，其中 \(U\) 表示全集。\(f,g\) 显然是镜像的，考虑怎么求 \(f_S\)。很容易想到的一个暴力做法是将这个过程看作一个二叉树，然后 \(dp_{t,x,i}\) 表示第 \(t\) 层第 \(x\) 个子树内部有 \(i\) 个 \(1\) 的方案数，合并就根据是否有 \(t\in S\) 来决定，如果 \(t\in S\) 那么两边的 \(i\) 必须一样，否则就是普通的卷积。算下复杂度，单次 DP 是 \(O(4^k)\) 的，再加上外面枚举 \(S\)，总共是 \(8^k\)，可以过 H1 但不能过 H2。可以使用 NTT 优化合并过程中的卷积过程做到 \(O(4^k·k)\)，但是稍微感觉一下就知道常数上天。

考虑找到合并过程中减少复杂度的突破口。容易发现的一点是如果 \(t\in S\)，那么第 \(t\) 层合并以后的 DP 数组里奇数位上的值都是 \(0\)，此时我们完全可以令 DP 数组长度除以二。更进一步地，如果第 \(t\) 层往下的层里有 \(c\) 个 \(\in S\) 的数，那么这一层 DP 数组其实只用开到 \(2^{t-c}\)。

这样我们重新优化一下 DP 状态：\(dp_{t,S,x,i}\) 表示，当前考虑到第 \(t\) 层，前 \(t\) 层中钦定的状态集合为 \(S\)（这里我们不在外层枚举 \(S\) 的原因是第 \(t\) 层的时候我们暂时不用考虑第 \(t\) 层以上的深度是否属于 \(S\)，所以 \(S\) 这一维只用开到 \(2^t\)），考虑第 \(x\) 棵子树，里面有 \(i·2^c\) 个 \(1\) 的方案数，其中 \(c=|S|\)，转移还是暴力。算下复杂度，\(\sum\limits_{t=0}^k2^{k-t}·\sum\limits_{S=0}^{2^t}4^{|S|}=O(5^k)\)，写一下发现能过。当然如果使用 NTT 优化可以做到 \(3^k·k\)，但是感觉没啥意思就不管了。

const int MAXK=15;
const int MAXN=8192;
const int MOD=998244353;
int k,n;
void solve(char *s,int *f){
	static int rev[MAXN+5];
	for(int i=0;i<(1<<k+1);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<k);
	for(int i=0;i<(1<<k+1);i++)if(i<rev[i])swap(s[i],s[rev[i]]); 
	static vector<vector<vector<int> > >dp[MAXK+3];
	for(int i=0;i<=k+1;i++){
		dp[i].clear();dp[i].resize(1<<i);
		for(int j=0;j<(1<<i);j++){
			dp[i][j].resize((1<<k+1-i));
			for(int l=0;l<(1<<k+1-i);l++){
				int c=i-__builtin_popcount(j);
				dp[i][j][l].resize((1<<c)+1);
			}
		}
	}
	for(int i=0;i<(1<<k+1);i++){
		if(s[i]!='1')dp[0][0][i][0]=1;
		if(s[i]!='0')dp[0][0][i][1]=1;
	}
	for(int i=1;i<=k+1;i++){
		for(int j=0;j<(1<<i-1);j++){
			for(int l=0;l<(1<<k+1-i);l++){
				int c=i-1-__builtin_popcount(j);
				for(int x=0;x<=(1<<c);x++)for(int y=0;y<=(1<<c);y++)
					dp[i][j][l][x+y]=(dp[i][j][l][x+y]+1ll*dp[i-1][j][l<<1][x]*dp[i-1][j][l<<1|1][y])%MOD;
				for(int x=0;x<=(1<<c);x++)dp[i][j+(1<<i-1)][l][x]=1ll*dp[i-1][j][l<<1][x]*dp[i-1][j][l<<1|1][x]%MOD;
			}
		}
	}
	for(int i=0;i<(1<<k+1)-1;i++)f[i]=dp[k+1][i][0][1<<(k-__builtin_popcount(i))];
}
int f[MAXN+5],g[MAXN+5];
char s[MAXN+5],t[MAXN+5];
int main(){
	scanf("%d%s%s",&k,s,t);n=(1<<k+1);reverse(t,t+n);
	solve(s,f);solve(t,g);int res=0;
	for(int i=0;i<=k;i++)for(int j=0;j<(1<<k+1);j++)if(~j>>i&1)
		f[j]=(f[j]-f[j|(1<<i)]+MOD)%MOD;
	for(int i=0;i<(1<<k+1);i++)res=(res+1ll*f[i]*g[(1<<k+1)-1-i])%MOD;
	printf("%d\n",res);
	return 0;
}