题解 P4831 【Scarlet loves WenHuaKe】

· · 题解

似乎见到的做法都是多项式\ln \exp的（

然而通过一些简单容斥可以轻易做到只用一次卷积，也并不需要对二分图结构进行奇怪讨论（

显然每行都有两枚石子。考虑枚举有两枚石子的列数，设其中k列有两枚石子，则有2(n-k)列有一枚石子，m-2n+k列为空。此时问题可以转化为二分图模型，左边有n个点，每个点度数为2，右边有k个点度数为2，2(n-k)个点度数为1，我们需要统计这个图的合法匹配数量（每个点恰好连出对应度数的边，且两个点之间最多连一条边）。

考虑将所有度数为2的点拆成两个度数为1的点，此时左右各有2n个点。如果直接在这4n个点之间连边，可能会出现重边的情况（设左边点a与点b原本同属于一个点，右边点c与点d原本同属于一个点，如果(a,c),(b,d)或(a,d),(b,c)连边，则对应原图中的重边情况）。可以用容斥去掉这一类情况，枚举重边的数量i，则总的匹配数量为：

S_k=\frac 1{2^{n+k}}\sum_i(-1)^i\binom ni\binom kii!2^i(2(n-i))!

这里的2^i是因为每一条重边在拆点后的新图中有两种连法，最后除以2^{n+k}是因为每一组拆出来的点交换顺序并不影响对应到原图中的连边方案。注意到S_k右边的和式只跟\binom ki有关，因此可以卷积计算，复杂度O(n\log n)。总答案为：

Ans=\sum_k\binom mk\binom {m-k}{2(n-k)}S_k