题解

思路

先看一个有 $s$ 个顶点、$e$ 条边的连通块。

做法

任选一个偶数大小的顶点集合，都恰有 $2^{e-s+1}$ 种边集使这些顶点的度数为奇数；奇数大小的集合则不可能出现。其原因是先在一棵生成树上从叶子向根依次决定边，偶数性保证最后根也满足要求，而不在生成树中的每条边都可以任意选择。因此，这个连通块对答案生成函数的贡献是 $2^{e-s+1}\sum_{j\text{ 为偶数}}\binom{s}{j}x^j$。

用并查集求出所有连通块大小，预处理阶乘和逆阶乘以计算组合数，再依次把每个连通块的上述偶数项多项式背包合并。所有连通块中自由选择非树边的总数为 $M-N+C$，其中 $C$ 是连通块数，所以最后将每一项统一乘以 $2^{M-N+C}$ 即为答案。

复杂度

合并过程中任意时刻只保留已经处理的顶点数，故时间复杂度为 $O(N^2)$，空间复杂度为 $O(N)$。