A. 环覆盖
条件等价于每个点度数都是偶数，不难写出恰好保留 \(k\) 条边时的答案：
\[[x^{\varnothing}y^k] \prod_{(u, v)} (1 + x^{\{ u, v \}} y) \]其中 \(x\) 这一维是 xor 卷积，\(y\) 这一维是加法卷积。
考虑经典套路，\((1 + x^S y)\) FWT 之后每位都是 \((1 \pm y)\)，乘起来之后每一位就都是 \((1 - y)^k (1 +y)^{m - k}\) 的形式，这个可以 \(O(m^2)\) 预处理出来。
对 \(\sum_{(u, v)} x^{\{ u, v \}}\) 进行 FWT，然后解一下方程就知道每位有几个 -1 了，然后就能知道 FWT 之后的数组了。
最后可以通过 FWT 的定义式求出答案，这样是 \(O(m2^n + m^2)\) 的。
然后发现本质不同的只有 \(O(m)\) 个，所以记一下每种有多少个就可以 \(O(n2^n +m^2)\)。
对于 FWT 的过程，发现枚举集合 \(S\) 之后要算的就是有多少条边恰好一个端点在 \(S\) 中，每加一个点 \(u\) 的时候只有与 \(u\) 相连的边会由变化，可以状压维护，这样就是 \(O(2^n +m^2)\) 的了。
H - Nim Counting
答案即为：
\[\sum_{S \neq \varnothing} [x^S] \sum_{1 \le k \le n} \left( \sum_{1 \le j \le n} x^{A_j} \right)^k \]由于 FWT 是线性变换，所以 FWT 之后对每一位都这么做，然后 IFWT 回去。
时间复杂度 \(O(n 2^n)\)。
D. Jzzhu and Numbers
答案为：
\[[x^{\varnothing}] \prod_{1 \le i \le n} (x^{U} + x^{\{ a_i \}}) \]其中乘法是 and 卷积。
发现 \((x^U + x^{\{ a_i \}})\) FWT 之后每位只会是 1 或 2，所以可以算出 \(\sum x^{\{ a_i \}}\) 的 FWT 数组后解方程得到。
然后 IFWT 回去即可。
时间复杂度 \(O(n2 ^n)\)。
C. Binary Table
考虑枚举行的状态，那么列就是 0 和 1 哪个少填哪个。
答案是 xor 卷积的形式。
G - 3^N Minesweeper
考虑 \(B \rightarrow A\) 的过程，实际上就是每位乘了个矩阵。
类似于 FWT，\(A \rightarrow B\) 就是每位乘上它的逆矩阵。
Ex - Distinct Multiples
进行互不相等容斥，对于一个集合 \(S\)，它的容斥系数是 \((-1)^{\lvert S \rvert - 1}(\lvert S \rvert - 1)!\)，方案数是 \(\left\lfloor\dfrac{m}{\operatorname{lcm}_{i \in S}(d_i)}\right\rfloor\)。
然后需要把每个集合组合起来，这个是集合幂级数 exp。
时间复杂度 \(O(n^2 2^n)\)。
P5406 [THUPC2019] 找树
首先最优化是假的，可以求出每种边权的方案数。
然后把每条边看成 \(x^{v_i}\) 之后做一遍 matrix-tree 即可。
求行列式的时候可以先把矩阵中的每个位置 FWT 过去，然后对每一位算行列式，最后 FWT 回去。
时间复杂度 \(O(n^3 2^w)\)。
标签：每位,le,2025.1,记录,卷积,sum,FWT,复杂度 From： https://www.cnblogs.com/definieren/p/18677012