P6076 [JSOI2015]染色问题题解

· · 题解

染色问题题解

前排提示：本题解的解释很细致，某些部分可能到了繁琐的程度，但是浅显易懂，请各位根据需求选择。

四个条件：

1.棋盘的每一个小方格既可以染色（染成 C 种颜色中的一种），也可以不染色。

2.棋盘的每一行至少有一个小方格被染色。

3.棋盘的每一列至少有一个小方格被染色。

4.每种颜色都在棋盘上出现至少一次。

转变成问题：用 C 种颜色， n 行满足条件，m 列满足条件。

那么如何切入问题呢？考虑用最简单的方式计算出的答案具有怎样的含义。

现在一共有 n\times m 个格子，每个格子一共有 c 种颜色 + 空白共 c+1中选择，共有 (c+1)^{nm} 个方案，而这对应的是：

最多用 C 种颜色，最多有 n 行，m 列满足条件的方案总数。

那么首先研究如何通过“最多有 x”的方案数得出“恰好有 x”的方案数：

令最多为 f_i，恰好为 g_i，则有：

g_i = \sum\limits_{j=1}^{i-1}(-1)^{i-j}C^j_if_j

我最开始困惑过一个非常愚蠢的问题，为什么不能直接通过 f_i - f_{i-1} 计算 g_i呢？

原因很简单， f_{i-1} 一共有 i 种，而这 i 种两两之间是有很多交集的，所以仍然需要容斥来解决。

那么如果设行，列满足情况时，最多用 i 种颜色的方案数为 f_i，那么答案即为：

f_c = \sum\limits_{i=1}^{c-1} (-1)^{c-i}C^i_cf_i

而计算 f_i，我们有两种途径：

一是按照刚才类似的方法再容斥两次得出答案，时间复杂度 O(nmc\log n)

第二种时间复杂度更加优秀，也体现了一种常见的思想：

先给出式子：

f_i = \sum\limits_{j=1}^n(-1)^{n-j}C_n^j((i+1)^j-1)^m

逐步解释：

1.枚举的 j :最多使 j 行满足条件。

2.(-1)^{n-j}:容斥，和刚才分析的类似。

3.C^j_n：n 行选 j 行，和刚才分析的类似。

4.((i+1)^j-1)^m：这个做法的精髓。对于某一列考虑选中的 j 行，每行都有 i+1 种填法，但因为题目要求，不能全部选空白，所以要减去 1，而对于每一列情况都相同，所以使用乘法原理，再带一个 m 次幂。

时间复杂度 O(nc\log n)