自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:57:13，当前版本为作者最后更新于2024-05-08 20:58:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先要判断什么样的状态是公平的。

可以发现，公平的状态最后一定是全部硬币都移除了，否则交换先后手是先手胜。

那么考虑能否给每个硬币一个权值，使得两人硬币权值和相等（也就是相差为 0）是状态公平的充要条件。

先给出赋权方法，对于一堆硬币，底部连续一段属于同一个人的硬币权值为 $1$，其余硬币权值是它下面硬币权值的 $\frac 1 2$。

例如 CCNNC 的权值为 $[1,1,\frac 1 2,\frac 1 4,\frac 1 8]$。

下面来说明为什么相差为 $0$ 的状态是公平的。

设当前硬币最小的权值为 $w$。

首先可以发现这样的硬币至少有 $2$ 枚，否则相差不为 $0$。

然后认为操作者移除自己的硬币减少相应的权值，移除对手的硬币增加相应的权值，最后权值小的就输了。

那么可以发现，这次移除硬币后，操作者权值至少减小 $w$。

因为根据等比数列求和，每个权值为 $x$ 的硬币上方对手的权值和不超过 $x-w$。

其次，能够做到只减少 $w$ 的权值，如果存在自己的硬币就直接移除，否则找到对面的权值为 $w$ 的硬币，将其下方第一个自己的硬币移除，可以发现这样权值也减少 $w$。

因此，先后手各减少 $w$ 的权值，权值相差依旧为 $0$。

接下来考虑怎么计数。

为了避免分数计算，将所有权值 $\times 2^{m-1}$。

特判掉 $m=1$ 的情况。

考虑数位 DP，因为每一堆石子底部连续段长度不同，考虑在枚举到该堆石子最低位时加入，并钦定底部是 $CC\cdots CN$ 还是 $NN\cdots NC$，同时记录权值 $\ge 2^{m-2}$ 的权值差。

设 $f_{i,j,k,l}$ 表示考虑了 $2^i$ 以下的位，加入了 $j$ 堆石子，$\ge 2^{m-2}$ 的权值差为 $k\times 2^{m-2}$，其余位的权值差为 $l\times 2^i$。

转移时枚举新加入的底部为 $CC\cdots CN$ 和 $NN\cdots NC$ 的堆的数量，再枚举这一位有多少 $C$。

注意到这 $3$ 个量联系并不大，可以分开 $3$ 次转移，每次 $O(n)$。

最后 $2^{m-2}$ 和全部相同的堆的转移也是类似的。

状态数为 $O(m\times n\times nm\times n)$，转移是 $O(n)$ 的。

所以时间复杂度 $O(n^4m^2)$，使用滚动数组后空间大小为 $O(n^3m)$，实测最大耗时在 $1s$ 以内。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7,V1=1536,V2=32,M1=V1*2+1,M2=V2*2+1;
int n,m,k,sum,C[35][35],f[33][M1][M2],g[33][M1][M2],h[33][M1][M2],t[33][M1],ans[35];
char s[25];
inline int md(int x){
	return x>=P?x-P:x;
}
inline void Add(int &x,int y){
	if((x+=y)>=P)x-=P;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;++i){
		scanf("%s",s);
		int t=m-1,fg=0;
		for(int j=0;j<m;++j){
			if(j&&s[j]!=s[j-1])fg=1;
			t-=fg;
			if(s[j]=='C')sum+=1<<t;
			else sum-=1<<t;
		}
	}
	n-=k,sum=abs(sum);
	for(int i=0;i<=n;++i)C[i][0]=1;
	for(int i=1;i<=n;++i)for(int j=1;j<=i;++j)C[i][j]=md(C[i-1][j]+C[i-1][j-1]);
	if(m==1){
		for(int i=0;i<=n;++i){
			if((i+sum&1)||sum>i)printf("0 ");
			else printf("%d ",C[i][i+sum>>1]);
		}
		return 0;
	}
	f[0][V1][V2]=1;
	for(int i=0;i<=m-2;++i){
		for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
			int w=f[j][k+V1][l+V2];
			if(!w)continue;
			f[j][k+V1][l+V2]=0;
			int v=2*(i+1)-1;
			for(int t=0;t+j<=n;++t)
				Add(g[j+t][k+V1+t*v][l+V2],1ll*w*C[j+t][t]%P);
		}
		for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
			int w=g[j][k+V1][l+V2];
			if(!w)continue;
			g[j][k+V1][l+V2]=0;
			int v=2*(i+1)-1;
			for(int t=0;t+j<=n;++t)
				Add(h[j+t][k+V1-t*v][l+V2],1ll*w*C[j+t][t]%P);
		}
		if(i==m-2)break;
		int o=sum>>i&1;
		for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
			int w=h[j][k+V1][l+V2];
			if(!w)continue;
			h[j][k+V1][l+V2]=0;
			if((l+j&1)!=o)continue;
			for(int t=0;t<=j;++t)
				Add(f[j][k+V1][(l+(j-2*t)-o>>1)+V2],1ll*w*C[j][t]%P);
		}
	}
	int o=sum>>m-2&1;
	for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k)for(int l=-V2;l<=V2;++l){
		int w=h[j][k+V1][l+V2];
		if(!w)continue;
		h[j][k+V1][l+V2]=0;
		if(l+k-o&1)continue;
		Add(t[j][(l+k-o>>1)+V1],w);
	}
	sum>>=m-1;
	for(int j=0;j<=n;++j)for(int k=-V1;k<=V1;++k){
		int w=t[j][k+V1];
		if(!w)continue;
		int v=k-sum;
		if(v%m!=0)continue;
		v/=m;
		for(int l=0;j+l<=n;++l)if(v<=l&&v+l>=0&&!(v+l&1))Add(ans[j+l],1ll*w*C[j+l][l]%P*C[l][v+l>>1]%P);
	}
	for(int i=0;i<=n;++i)printf("%d ",ans[i]);
	return 0;
}