【每日一题】4月10日题目精讲组合、容斥

题号 NC13229
名称二分图染色
来源美团2017年CodeM大赛-初赛A轮
 戳我进入往期每日一题汇总贴~

注：如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

今天这个题看来是偏难了……

这个题的第一个难点也是它设计得最巧妙的一个点，在于要把找个二分完全图的染色问题向二维棋盘格子上的行列覆盖转化。（如果你学过二分图匹配并做过一些相关的练习，其实你是应该能想到的——二分图匹配相关的问题往往是：棋盘格子上的行列覆盖转化成二分完全图匹配，1*2的小骨牌覆盖转化为棋盘格子黑白染色之后的二分图匹配，这个题只是反过来转换了。）

原题是左右两边各有n个点的完全二分图每条边选一个颜色来染，我们把问题转化为在n*n的棋盘上放棋子（棋盘的行和列分别对应二分图左边的点和右边的点，棋子对应的是边）；原题是边染成三种颜色而且实际上绿色没啥用，我们可以认为绿色是没染色的，这样子的话要转换到棋盘上其实就是选一些格子放红色或者蓝色的棋子；原题要求任意两条红边不共享端点、同时任意两条蓝边也不共享端点，转化之后就是任意一行一列不能有两个颜色相同的棋子。

总结一下就是说：题目变成了，在n*n的棋盘上选择若干个格子放置红色或者蓝色的棋子，任意一行或者任意一列没有两个相同颜色的棋子。

先考虑只有一种颜色的情况，如果我们用 $F_{n}$ 来表示棋盘大小为n*n时候的答案，那显然有 $F_{n}=\sum^{n}_{i=0}C^{i}_{n}A^{i}_{n}$ 种方案（n行里面选若干行，每一行再对应选若干列，选列的时候就是排列而不是组合了）

两种颜色的话，可以在 $F_{n} \times F_{n}$ 中减去两种棋子有至少一个在一个格子的情况。这个是需要容斥的，因为 $C_n^1A_n^1(F[n-1])^2$ 表示的并不是至少有一个格子里有两个棋子的方法数，因为当有两个即两个以上的格子里有两个棋子的时候，对于每一个格子X有两个棋子的情况，在 $C_n^1A_n^1$ 里面都贡献了一个1，这个时候是X和另外的若干个格子里有两个棋子，而当 $C_n^1A_n^1$ 的另一个1即表示格子Y里面有两个棋子的时候 $(F[n-1])^2$ 里面也是有之前那个X的，于是就算重复了。所以需要使用容斥原理（大家一定要去手推一下！），最后算出来是 $(-1)^kC_n^kA_n^k(F[n-k])^2$

有取模操作，所以 $C_n^kA_n^k$ 都可以提前用乘法逆元求好，而F（n）也要提前求，并且得 $O（n）$ 的求……也就是说上面那个组合公式不能用。

我们来考虑一下F(n）能不能递推。即从F[n-1]算F[n] 。

从n-1到n的时候，格子增加了一行一列一共2n-1个，如果我们在这些格子里面只放一个棋子进去，就有2n-1个方案，加上一个都不放的1种，就是2n种。但是这样的方法里面会有矛盾出现，即我当前放的这一个和它所在行（如果是放在最后一列的话）、所在列（放在最后一行）的棋子矛盾，方案数是 $2 \times (n-1)^2 * F(n-2)$ ，如图：
图片说明