$Description$
在一个m行n列的棋盘里放一些彩色的棋子,使得每个格子最多放一个棋子,且不同
颜色的棋子不能在同一行或者同一列。有多少种方法?
$Solution$
由于不同色的棋子不能放在同一列,每种颜色的棋子的放置是相互独立的。
因此可以考虑dp处理。
设$f[i][j][k]$:前k种颜色的棋子占领了i行j列的方案数。
$C[i][j]$:组合数(i个中选j个)。
设$g[i][j][k]:$k个棋子恰好占据i行j列的方案数。
$a[k]:$第k种棋子的个数。
由于一个棋子至少要占据一行一列,我们枚举$l<i,r<j$
$f[i][j][k]=\Sigma f[l][r][k-1]× C[n-l][i-l]× C[m-r][j-r]× g[i-l][j-r][a[k]]$
$Explanation:$对于$f[l][r][k-1]$中已经选中的l行r列不动,从剩下的n-l行中任意选择i-l行放置棋子,列同理。
其他都好办,但我们发现$g[i][j][k]$没法直接求。
通过观察,我们发现在i行j列中放k个棋子的方案数很好求($C[i*j][k]$),不合法的方案就是实际上占领的行数<i或列数<j。
所以直接枚举$l<=i,r<=j(l×r<i×j)$
$g[i][j][k]=C[i× j][k]-\Sigma g[l][r][k]× C[i][l]× C[j][r]$
$Talk\;is\;Cheap…$
1 | include<cstdio> |