题解：P3158 [CQOI2011] 放棋子
残阳如血
·
·
题解
\textbf{Description}
在一个 n 行 m 列的棋盘中放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能再同一行或同一列，求方案总数。
\textbf{Solution}
设 a_k 表示颜色为 k 的棋子的数量。
令 f_{i,j,k} 表示使用前 k 种颜色的棋子，填入任意 i 行 j 列的方案数。
令 g_{i,j,k} 表示用任意 k 个同色棋子，填入任意 i 行 j 列的方案数。
$$
g_{i,j,k}=
{i\cdot j\choose k}-
\sum\limits_{l=1}^{i}\sum\limits_{r=1}^{j}{i\choose l}{j\choose r}g_{l,r,k}
$$
预处理 $g$ 完成后，就可以转移 $f$：
$$
f_{i,j,k}=
\sum\limits_{l=0}^{i-1}\sum\limits_{r=0}^{j-1}
{n-l\choose i-l}{m-r\choose j-r}
f_{l,r,k-1}\cdot g_{i-l,j-r,a_k}
$$
答案即为
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}f_{i,j,c}
$$
### $\textbf{Code}