你细品巨大多太阳的题解，虽然看不懂，但是发现挺有道理的。
容易发现，一个无向图是可环覆盖图，当且仅当所有点的度数为偶数。所以将一条边 \((u,v)\) 看作集合 \(\{u,v\}\)，相当于求选出 \(i\in [0,m]\) 个集合 \(\{u_i,v_i\}\)，其对称差为 \(\varnothing\) 的方案数。
考虑集合幂级数，由于有 \(i\) 的限制需要带一个形式幂级数的元，即令 \(F(x,y)=\prod\limits_{i=1}^m(1+x^{\{u_i,v_i\}}y)\)，那么 \(\text{ans}_i=[x^{\varnothing}y^i]F(x,y)\)。\(x\) 的乘法定义为对称差（异或）卷积，而 \(y\) 的乘法定义为加法卷积。
将 \(x^S\) 的系数当做关于 \(y\) 的形式幂级数，将 \(F(x,y)\) 简写为 \(F\)，则我们只需要求出 \([x^{\varnothing}]F\)，考虑 \([x^{\varnothing}]F=\frac{1}{2^{n}}\cdot \sum\limits_{S}[x^S]\text{FWT}(F)\)：
\[[x^{S}]\text{FWT}(F)=\prod\limits_{i=1}^m[x^S]\text{FWT}(1+x^{\{u_i,v_i\}}y) \]注意到 \(\text{FWT}\) 算子的定义 \([x^S]\text{FWT}(F)=\sum\limits_{T}(-1)^{|S\cap T|}[x^T]F\)。由于 \(T=\varnothing\) 时 \((-1)^{|S\cap T|}=1\)，所以 \([x^{S}]\text{FWT}(1+x^{\{u_i,v_i\}}y)=1+y/1-y\)。
于是 \([x^S]\text{FWT}(F)\) 一定能写成 \((1+y)^{m-a_S}(1-y)^{a_S}\) 的形式。考虑到 \(a_{S}\) 的意义为 \(|\{u_i,v_i\}\cap S|=1\) 的 \(i\) 的个数，容易发现只有 \(O(m)\) 种，这启示我们对于每个 \(i\in [0,m]\) 计数 \(f_i\) 表示有多少个 \(S\) 的 \(a_{S}=i\)，答案就是 \(\sum\limits_{i=0}^m(1+y)^{m-i}(1-y)^if_i\)。
考虑如何求出 \(f_i\)。枚举点 \(u\)，每次选择在 \(S\) 中加入/不加入点 \(u\)，并动态维护此时的 \(a_S\)。那么 \(a_S\) 增加所有 \(u\in S\) 且 \(v\neq S\) 的边的个数即可。
复杂度 \(O(2^n+\text{poly}(m))\)。
标签：5089,limits,text,sum,cap,varnothing,FWT,QOJ From： https://www.cnblogs.com/Ender32k/p/17727391.html