【每日一题】二分图染色

Solution

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

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

而在另外一边，选择个点的顺序不同会产生不同的方案，这部分的方案数为；

所以，个点的完全二分图只连条红色/蓝色边的方案数为；

总的方案数即为。

那么，染两种颜色的方案数就很明显了：。

这个重复部分，利用(我现学的)容斥知识可以知道，是；

故而。

注意到，这个需要的复杂度来计算，这显然是不可接受的。

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

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

1. 因为多了一行一列共个格子，产生了种选择(不选也是一种情况)；

2. 若是选择的格子在前行/列，那么可能存在一个同一行/列的格子已经被选中了，这个格子的位置有种情况；

3. 在抠掉重复的这个格子(以及新增的一行一列)之后，剩余的阶方格图必须要是合法状态，有种情况；

所以，可以得出，这样就可以递推求解了。(注意第点中，因为对称性，只需考虑在前行的情况即可，不需考虑前列的情况)

Code

戳这里