[AHOI 2009] 中国象棋

题目传送-Luogu2051

题目传送-BZOJ1801

题意：

给一个n*m的棋盘，要求每一行列只能有不超过3个棋子，问方案数(棋子数任意)
(n,m le 100)

题解：

这题唯一的脑洞之处就只有状态了
观察到每一行/列最多只能有2个，在这上面做手脚
设置(f_{i,j,k})表示前i行完成，还有j列可以放2个，k列可以放1个
转移显然

过程：

很顺利，除了状态想了一会儿

代码：

const int N=110;
const ll P=9999973;
int n,m;
ll f[N][N][N],C[N][N],ans;
signed main() {
	read(n); read(m);
	for(int i=0;i<=100;i++) C[i][0]=1;
	for(int i=1;i<=100;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	f[0][m][0]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;j+k<=m;k++)
				if(f[i][j][k]) {
					ll val=f[i][j][k];
					(f[i+1][j][k]+=val)%=P;// NUL
					if(j) (f[i+1][j-1][k+1]+=val*j)%=P;//j
					if(k) (f[i+1][j][k-1]+=val*k)%=P;//k
					if(j) (f[i+1][j-1][k]+=val*j%P*k%P)%=P;//j k
					if(j>1) (f[i+1][j-2][k+2]+=val*C[j][2])%=P;
					if(k>1) (f[i+1][j][k-2]+=val*C[k][2])%=P;
				}
	for(int i=0;i<=m;i++)
		for(int j=0;i+j<=m;j++)
			(ans+=f[n][i][j])%=P;
	printf("%lld
",ans);
	return 0;
}

用时：15