Description
你有一个N×M的网格和C种颜色,要求给每个格子染色,并且使得任意两行的染色方案不完全相同,任意两列也是。求方案数。
1≤N,M,C≤4000。
Solution
TopCoder Arena真难用……
光限制列或者光限制行还算好做,但是同时限制就要掀桌子了。
所以我们不妨先考虑只去满足行的限制,这样的方案数为n!\binom{c^m}{n},注意到这个东西的组合意义就是说明了(列意义上的)等价类至多有m个时的方案数,如果说至多有i个那么方案数就是n!\binom{c^i}{n},不妨将其记为f_i。
现在我们很好做“至多”的方案数,那么要求“恰好”很显然就需要容斥力,,,注意到f_i = \sum_{j = 1}^i\begin{Bmatrix}i\\ j\end{Bmatrix}g_j,这里的g_j表示的是恰好有j个等价类的方案数,移项得g_i = f_i - \sum_{j = 1}^{i - 1}\begin{Bmatrix}i\\ j\end{Bmatrix}g_j,用这个式子递推就好了。
Code
1 |
|