[CQOI2011]放棋子

题目描述

在一个 $m$ 行 $n$ 列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列，有多少种方法？

例如，$n=m=3$，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。

$1\le n,m\le 30$，$1\le c\le 10$，总棋子数 $\le \max (250,n\times m)$。

思路点拨

计数问题考虑 $dp$ ，这是本题的难点。因为数据范围的误导不好想到这个。我们看看我们需要定义那些状态，由于每一行，每一列只能填一种颜色，所以行列要记录。又因为我们需要一个个将元素插入棋盘中，所以插入到了那种颜色的棋子也是必要的。最终我们获得了初步的状态： $f[i][j][k]$ 表示填到了第 $i$ 中棋子，已经有 $j$ 行，$k$ 列的棋盘上使用棋子。

接下来考虑转移吧，我们可以枚举每一中颜色的棋子的 "统治范围"，也就是那些行列只包含这种颜色。可以得到转移式：

\[f[i][j][k]=\sum_{x=0}^j \sum_{y=0}^k f[i-1][x][y]\times C_{n-x}^{j-x} C_{m-y}^{k-y} \times w_{i-x,j-y} \]

先解释一下 $C_{n-x}^{j-x} C_{m-y}^{k-y}$ ,这是因为转移中，对于第 $i$ 中颜色，它的统治范围是 $i-x$ 行，$j-y$ 列。那么我们显然是要从剩余的 $n-x$ 行， $m-y$ 列中选取的。转移式中还有一个转移的贡献 $w_{i,j}$ ,相信读者们可以猜出来这是什么意思： $w_{x,y} $ 表示在一个 $x\times y$ 的矩阵中填入 全部的 颜色 $i$ 棋子的方案数。

Q:为什么是一个 $x \times y$ 的矩阵呢？

A:这是因为我们转移时枚举了 $x,y$ ,也就是棋子 $i$ 的统治范围，那么我们多出的行数就是 $i-x$行， $j-y$ 列。显然，在这些行列中可以使用的格子只有 $(i-x) \times (j-y )$ 这么多。

有的童鞋就想（一开始的我），这不是直接 $C_{xy}^{cnt_i} =w_{x,y}$ （其中 $cnt_i$ 表示颜色 $i$ 的数量）就可以了吗？然后给出了如下代码：

f[0][0][0]=1;
for(int k=1;k<=col;k++)
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int x=0;x<=i;x++)
				for(int y=0;y<=j;y++)
					f[k][i][j]=(f[k][i][j]+f[k-1][x][y]*C((i-x)*(jy),a[k])%mod*C(i,x)*C(j,y)%mod)%mod;
	cout<<f[col][n][m];

OK啊这只有 $50 $ 分（~~这么多我已经很满意了~~）。

这就是因为，刚刚我们的 $w$ 的定义不够严谨。如果在这 $x \times y$ 的矩阵中，有某一行或者某一列没有放棋子，那么这样会算重的。为什么会算重呢？如果一行没有东西，那么在别的转移中我是不是也可以多选出这一行，那么这样不就会有问题吗？这和我们的定义是有一定出入的。这一点比较难被发现。我们重新定义 $w_{x,y}$ 吧，就是加上每一行每一列都 必须有 棋子的方案。

这样不好搞，因为每一行列都有至少一个棋子的限制。这样的问题我们很容易想到使用二项式反演转换成一般的问题。我们定义 $f(x)$ 表示刚好 $x$ 行满足条件的方案数。 $g(x)$ 表示 不超过 $x$ 行满足条件的方案数。那么有：

\[g(x)=\sum_{i=0}^x C_{x}^i f(x) \]

反演得：

\[f(x)=\sum_{i=0}^x (-1)^{x-i} C_{x}^i g(x) \]

考虑 $g(x)$ 得求法。我们先补充完整 $g(x)$ 得定义：$g(x)$ 表示 不超过 $x$ 行满足条件，全部 $y$ 列都满足条件得方案数。我们在此基础上设， $h(y)$ 表示在 不超过 $x$ 行满足条件，不超过 $y$ 行满足条件得方案数。

那么有：

\[h(y)=\sum_{i=0}^{y} C_{y}^i g(i) \]

反演的：

\[g(y)=\sum_{i=0}^{y} (-1)^{y-i}C_{y}^i h(i) \]

我们发现 $h(y)$ 的取值十分简单求出，就是 $C_{xy}^{cnt_i}$ ，$cnt_i$ 表示颜色 $i$ 的数量，为了节省变量名，下文称 $cnt$ 。

我们将刚刚的式子回代，那么就有：

\[f(x)=\sum_{i=0}^x\sum_{j=0}^{y} (-1)^{x-i+y-j}C_{x}^{i}C_{y}^{j}C_{ij}^{cnt} \]

这个式子 $O(nm)$ 求就可以了。每一次转移我们都需要求出每一个 $w_{x,y}$ 的值域。所以这部分在每一次转移的时候是 $O((nm)^2)$ 的。

现在我们会求出转移时的贡献 $w$ 了，那么转移应该是会写与懒得写的区别了：

f[0][0][0]=1;
for(int k=1;k<=col;k++){
	memset(g,0,sizeof(g));
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int x=0;x<=i;x++)
				for(int y=0;y<=j;y++)
					g[i][j]=(g[i][j]+(C[i][x]*C[j][y]%mod*pw[i-x]*pw[j-y]+mod)%mod*C[x*y][a[k]])%mod;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int x=0;x<=i;x++)
				for(int y=0;y<=j;y++)
					f[k][i][j]=(f[k][i][j]+f[k-1][x][y]*g[i-x][j-y]%mod*C[n-x][i-x]%mod*C[m-y][j-y]%mod)%mod;
}