【每日一题】二分图染色

Solution

首先，我们考虑只染红色/蓝色的情况。

假设当前染了 $k$ 条边，那么一定在其中一边选择了 $k$ 个点，这部分的方案数为 $C_{n}^{k}$ ；

而在另外一边，选择 $k$ 个点的顺序不同会产生不同的方案，这部分的方案数为 $A_{n}^{k}$ ；

所以， $n$ 个点的完全二分图只连 $k$ 条红色/蓝色边的方案数为 $f_{k}(n) = C_{n}^{k} \cdot{A_{n}^{k}}$ ；

总的方案数即为 $f(n) = \sum_{i=0}^{n} f_{i}(n) = \sum_{i=0}^{n} C_{n}^{i} \cdot{A_{n}^{i}}$ 。

那么，染两种颜色的方案数就很明显了： $result = f(n)^{2} - (红蓝边集重复的部分)$ 。

这个重复部分，利用~~(我现学的)~~容斥知识可以知道，是 $\sum_{i=1}^{n} (-1)^{i+1}\cdot{}C_{n}^{i}\cdot{}f_{i}(n) \cdot{f(n-i)^{2}}$ ；

故而 $result = f(n)^{2} + \sum_{i=1}^{n} (-1)^{i} \cdot{C_{n}^{i}} \cdot{f_{i}(n)} \cdot{f(n-i)^{2}}$ 。

注意到，这个 $f(n)$ 需要 $O(n^{2})$ 的复杂度来计算，这显然是不可接受的。

实际上，这个 $f(n)$ ，就是“给定一个 $n$ 行 $n$ 列的方格图，选择其中的若干个格子，满足任意两个选中的格子不在同一行/同一列”的方案数(lightOJ-1005, 选择 $k$ 个格子的版本)。

基于此，考虑如何从 $n-1$ 的结果转移到 $n$ 的结果：

所以，可以得出 $f(n) = 2n \cdot{f(n-1)} - (n-1)^{2} \cdot{f(n-2)}$ ，这样就可以 $O(n)$ 递推求解了。(注意第 $2$ 点中，因为对称性，只需考虑在前 $n-1$ 行的情况即可，不需考虑前 $n-1$ 列的情况)