菜王的 blog

这能红？

首先发现重边是没有影响的，且边的端点顺序不重要，所以考虑求出有 $i$ 个点 $j$ 条边的简单二分图个数 $f_{i, j}$，则答案为 $2^m \sum_{i = 0}^{L(n)} {m \brace i} f_{n, i}$，可以 $O(n^4 \log m)$ 计算，其中 $L(n) = \lfloor \frac n2 \rfloor \lceil \frac n2 \rceil$，即 $n$ 个点的二分图的最大可能边数。

至于计算 $f_{i, j}$，由于我们不关心二分图的染色情况，所以为了避免重复计数，我们钦定：对于每个连通块，编号最小的点染成白色。如果对染色的角度考虑的话是不好计数的，所以我们对连通的二分图进行计数，最后再将连通块拼起来。即设 $g_{i, j}$ 为有 $i$ 个点 $j$ 条边的简单连通二分图个数，枚举 $1$ 号点所在的连通块大小及边数，则有：

$f_{i, j} = g_{i, j} + \sum_{k = 1}^{i - 1} \sum_{l = 0}^j \binom{i - 1}{k - 1} g_{k, l} f_{i - k, j - l}$

计算 $g_{i, j}$ 可以使用类似有标号无向连通图计数的思想进行容斥，枚举 $1$ 号点所在的连通块大小及边数，则有：

$g_{i, j} = h_{i, j} - \sum_{k = 1}^{i - 1} \sum_{l = 0}^j 2\binom{i - 1}{k - 1} g_{k, l} h_{i - k, j - l}$

因为剩下一部分的二分图可以选择令最小标号点与 $1$ 染成同色 / 异色。

其中 $h_{i, j}$ 为有 $i$ 个点 $j$ 条边，满足连通图的染色条件（即 $1$ 染成白色），但是不一定连通的简单连通二分图个数，枚举与 $1$ 号点同色的点个数 $x$，有：

$h_{i, j} = \sum_{x = 1}^i \binom{i - 1}{x - 1} \binom{x(i - x)}{j}$

时间复杂度为 $O(n^6 + n^4 \log m)$，常数很小可以通过。