自动搬运

查看原文

来自洛谷，原作者为

	Larunatrecy 举杯邀明月，对影成三人。

搬运于2025-08-24 22:59:12，当前版本为作者最后更新于2024-06-01 19:09:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，对于一个确定的图，我们先考虑怎么计算最大匹配数，设图中一共有 $m$ 个连通块，第 $i$ 个大小为 $s_i$，那么最大匹配数有显然上界 $\sum_i \lfloor \frac{s_i}{2}\rfloor$，并且我们总是可以取到这个上界的，这一点不难证明。

现在考虑计数，因为 $\lfloor \frac{s_i}{2}\rfloor=\frac{s_i-[s_i\bmod 2\equiv 1]}{2}$，我们只需要对 $s_i,[s_i\bmod 2\equiv 1]$ 分别求和就行了，前者就是 $nm2^{nm-1}$，后者就是求有奇数个点的连通块个数。

考虑一个二分图，左部点代表所有行，右部点代表所有列，那么每个原图的点就代表了一条新图中的边，并且原图和新图的连通关系是等价的，我们只需要求所有这样的二分图中的奇数条边的连通块个数和就行了，只要能求出 $f_{i,j}$ 表示 $i$ 个左部点，$j$ 个右部点的奇数条边的连通二分图个数即可，设其二元生成函数为 $F$。

设 $i$ 个左部点，$j$ 个右部点的，奇数/偶数条边的二分图的二元生成函数为 $G_1,G_0$，那么有：

$F=\frac{\ln(G_0+G_1)-\ln(G_0-G_1)}{2}$，因此只需要实现二元多项式的 Ln 就可以通过了。

多组询问也不难通过二维 FFT 做，因此复杂度为 $O(n^2\log n)$，但是因为常数过大所以范围开的比较小。