P10563

· · 题解

首先，对于一个确定的图，我们先考虑怎么计算最大匹配数，设图中一共有 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，那么有：

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