自动搬运

查看原文

来自洛谷，原作者为

	ez_zjt 哈哈

搬运于2025-08-24 22:04:24，当前版本为作者最后更新于2019-04-28 20:26:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

似乎见到的做法都是多项式$\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$$