## 《环覆盖》解题报告
## 题目大意
### 题目描述
**形式化题意**：给定一张 $n$ 个点，$m$ 条边的简单无向图，对每个 $i\in [0,m]$，计算它只保留 $i$ 条边，使得剩下的图是一个可环覆盖图的方案数。可环覆盖的定义是，可以将边集划分成若干个子集，使得每个子集都形成一个环。

答案对 $10^9+7$ 取模。
### 数据范围
对于所有数据，$1\le n\le 25,0\le m\le \dfrac{n(n-1)}{2}$。

Subtask 1（5pts）：$n,m\le 20$。

Subtask 2（15pts）：$n\le 20,m\le 40$。依赖 Sub 1。

Subtask 3（15pts）：$n=25,m=45$。

Subtask 4（30pts）：$n\le 20$。依赖 Sub 2。

Subtask 5（35pts）：无特殊限制。依赖 Sub 4。

时间限制：1s

空间限制：512MB
## 解题过程
### 算法 1
首先注意到一个图是可环覆盖的，当且仅当它的每个点度数均为偶数。充分性是显然的。必要性可以通过对每个连通块构造欧拉回路证明。

搜索边集的每个子集，利用上述条件判断其是否合法，时间复杂度 $O(n+2^m)$。期望通过子任务 1，获得 5 分。
### 算法 2
使用动态规划，设 $dp_{i,j,S}$ 表示在前 $i$ 条边中保留了 $j$ 条，使得它们构成的图中，度数为奇数的点集恰为 $S$ 的方案数。转移是平凡的。

时间复杂度 $O(2^nm^2)$，期望通过子任务 1、2，获得 20 分。
### 算法 3
称合法的边子集为“环路”，这是图论中一个著名的概念。通过对节点度数的奇偶性分析容易说明，环路集合关于集合对称差运算是封闭的。

将环路看成一个长为 $m$ 的 01 向量，则环路集合可以看成一个向量空间。接下来构造这个空间的一组基。

不妨只讨论连通图。任取一棵生成树，对于一条非树边，其本身加上其两端点在树上的路径，构成一个环路。我们称这样的环路为基础环路。

而全体非树边会如是构成 $m-n+1$ 个基础环路，由于每条非树边都恰在一个基础环路中，容易说明基础环路对应的向量线性无关。而任取一个环路，其含有的每条非树边对应的基础环路作对称差，必然得到这环路本身。

于是，我们说明了一张连通图的环路数量为 $O(2^{m-n+1})$。按上述构造可以暴力枚举每个环路以计算答案，使用 bitset 优化集合对称差，时间复杂度 $O(2^{m-n+1}\dfrac{m}{w})$（其中 $w$ 为字长），期望通过子任务 3，结合算法 2 可以得到 35 分。
### 算法 4
在算法 2 的基础上加以优化。我们使用集合幂级数描述上述 dp，则所求即为
$$[x^{\varnothing}]\prod_{(u,v)\in E}(1+x^{\{u,v\}}y)$$
其中未定元 $x$ 一维进行的是集合幂级数的异或卷积，而 $y$ 一维进行的是普通加法卷积。我们记 $H=\prod_{(u,v)\in E}(1+x^{\{u,v\}}y)$。

对 $x$ 一维作 $FWT$。观察 $[x^S]FWT(1+x^{\{u,v\}}y)$，必然为 $1+y$ 或 $1-y$。因此，$[x^S]FWT(H)$ 将形如 $(1+y)^a(1-y)^{m-a}$。

先对于每个 $a\in[0,m]$ 预处理出 $(1+y)^a(1-y)^{m-a}$，时间复杂度 $O(m^2)$。然后枚举 $S$，容易根据 FWT 的定义式计算出 $[x^S]FWT(1+x^{\{u,v\}}y)$ 是 $1+y$ 还是 $1-y$。

于是，此时容易在 $O(2^n m)$ 的时间内处理出 $FWT(H)$，进而根据 IFWT 的定义式计算答案。总时间复杂度 $O(2^n m+m^2)$，期望通过子任务 1、2、4，结合算法 3 得到 65 分。

（注：文中 “FWT 的定义式” 是指 $[x^S]FWT(F)=\sum_{T} (-1)^{|S\cap T|}[x^T]F$）
### 算法 5
优化算法 4 的瓶颈。

注意到我们无需处理出整个 $FWT(H)$，而只需计算 $[x^{\varnothing}]H$。根据 IFWT 定义式，也就是只需计算 $\sum_S [x^S]FWT(H)$。于是，对于每个 $a$ 处理出使 $[x^S]FWT(H)=(1+y)^a(1-y)^{m-a}$ 的 $S$ 的个数，即可据此在 $O(m^2)$ 的时间内计算答案。

枚举 $S$ 后，注意到只需计算出有几条边恰有一个端点在 $S$ 中。尝试维护这样的边的集合 $A$。在 $S$ 中增删一个点 $u$ 的时候，只有与 $u$ 相邻的边在 $A$ 中的存在情况会发生改变，且容易使用 bitset 维护。于是，枚举 $S$ 时采用合适的方式，即可在 $O(2^n)$ 的时间复杂度内维护对应的 $A$ 的大小。

总时间复杂度优化至 $O(2^n+m^2)$。期望通过所有子任务，得到 100 分。
### 算法 6
根据算法 3 中的分析，本题要计算的无非是对每个 $i\in[0,m]$，环路空间中 $1$ 的个数恰为 $i$ 的向量个数。

参考 CF1336E2，考虑该空间的正交补空间，即为断集空间。环路空间和断集空间的概念容易在图论书籍中找到。由于断集空间维数是 $n-1$，套用 CF1336E2 的做法可以做到 $O(2^n+poly(m))$ 的时间复杂度，在此不再赘述。

事实上，将算法 5 和算法 6 的过程进行比较，可以发现在本题中二者殊途同归，算法流程几乎完全相同。
## 参考资料
[1] [Codeforces 1336E2 题解](http://codeforces.com/blog/entry/76099)。