QOJ5089

标签：frac sum ifwt QOJ5089 fwt xor

关于 fwt 的直接计算式：

1. or：\(fwt(a)_i=\sum_{j\subseteq i}a_j\)
2. and：\(fwt(a)_i=\sum_{i\subseteq j}a_j\)
3. xor：\(fwt(a)_i=\sum_{j}(-1)^{|i\cap j|}a_j\)

关于 ifwt 的直接计算式：

1. or 和 xor 就是子集反演（容斥）
2. xor 发现就是每次都会多乘一个 \(\frac{1}{2}\) ：\(ifwt(a)_i=\frac{1}{|a|}\sum_{j}(-1)^{|i\cap j|}a_j\)

---

能环覆盖充要条件为每个点的度数均为偶数。

相当于要求解 \([x^{\empty}y^{i}]\prod_{(u,v)\in E}(1+x^{\{u,v\}}y)\)。关于 x 的是异或卷积。

暴力的，先进行 \(|E|\) 次 fwtxor。但是不难发现 fwt 后每一位的多项式只有两种可能 \((1-y)\) 或者 \((1+y)\)。

也就是最终卷积结果的 fwt 后的每一位都是形如 \((1+y)^a(1-y)^{m-a}\) 形式。如果我们知道每一位的 \(a\)，那么问题就解决了。

而求解 \(a\) 可以用一个简单的状压 dp。一条边 \((u,v)\)，在只包含 \(u\) 或 \(v\) 的时候贡献一个 \((1-y)\) 其余时间均为 \((1+y)\)。

复杂度为 \(O(2^{n}+poly(m))\)。

Submission.

标签：frac,sum,ifwt,QOJ5089,fwt,xor
From： https://www.cnblogs.com/1l2u3o/p/18382605