[学习笔记]子集卷积

前置知识

• FMT：对于两个下标在 \([0,2^n)\) 的数组 \(f\) 和 \(g\)，求：

• \[h_i=\sum_{j\text{ or }k=i}f_jg_k \]

• 可以做到 \(O(2^nn)\)

• 限于博主水平，这里不放该前置算法的流程，请自行百度

引入

• 对于两个下标在 \([0,2^n)\) 的数组 \(f\) 和 \(g\)，求：

• \[h_i=\sum_{j\text{ and }k=\varnothing,j\text{ or }k=i}f_jh_k \]

• \(j,k\) 的条件即为集合 \(j\) 和 \(k\) 恰好拼成集合 \(i\)

• \(h\) 为 \(f\) 和 \(g\) 的子集卷积

• 可以做到 \(O(2^nn^2)\) 的复杂度

算法流程

• 下面用 \(|i|\) 表示 \(popcount(i)\)，即 \(i\) 二进制下 \(1\) 的个数

• 注意到 \(j\text{ and }k=\varnothing\) 时必有 \(|j|+|k|=|j\text{ or }k|\)

• 故引入占位多项式：

• \[F_{i,j}=\begin{cases}f_j & |j|=i\\0 & |j|\ne i\end{cases} \]

• 求 \(H_{i,j}\) 时，可以枚举拼成 \(j\) 的两个集合大小 \(i_1\) 和 \(i_2\)，我们有：

• \[H_{i,j}=\sum_{i_1+i_2=i}\sum_{a\text{ or }b}F_{i_1,a}G_{i_2,b} \]

• 也就是：

• \[H_i=\sum_{i_1+i_2=i}F_{i_1}\bigotimes G_{i_2} \]

• \(\bigotimes\) 为或卷积

• \(H_i\) 中可能会有 \(1\) 的个数小于 \(i\) 的项为 \(0\)，但这并不重要

• 对于每个 \(0\le i\le n\)，把 \(F_i\) 和 \(G_i\) 做一遍 FMT，作一遍上式之后得到 \(H\) 再 IFMT 回来即可得到 \(h\)

• \(O(2^nn^2)\)

拓展

• 观察这个式子

• \[H_i=\sum_{i_1+i_2=i}F_{i_1}\bigotimes G_{i_2} \]

• 发现 \(\sum_{i_1+i_2=i}\) 就是我们常见的多项式卷积！

• 于是把 \(F\) 视为一个 \(n\) 次多项式（每个项的系数都是一个集合幂级数，即 \(F_i\)）

• 也就是占位多项式，我们就可以进行求逆甚至 \(\ln\) 和 \(\exp\)

• 求逆可直接使用 \(g_i=\frac{1-\sum_{j=0}^{i-1}g_jf_{i-j}}{f_0}\) 进行递推

• 对于 \(\ln\) 我们有 \(g=\ln f=\frac{f‘}f\)

• 对于 \(\exp\) 我们有 \(g=\exp f\) 则 \(g‘=gf‘\)，可以递推出 \(g\) 的每一项

LOJ#3165「CEOI2019」游乐园

• 给定一个 \(n\) 节点 \(m\) 边的有向图，可以将部分边反向，求使得原图无环的所有方案下，翻转的边数之和，\(n\le 18\)

• 首先无环图所有边反向之后还是无环图，这样的两个合法图一一对应并且翻转的边数之和为 \(m\)，故答案为方案数乘 \(\frac m2\)

• \(f_S\) 表示点集 \(S\) 无环的方案数

• 一个图无环当且仅当这个图能够拓扑排序，严谨地说就是每次删掉图中入度为 \(0\) 的点集可以删完所有点

• 考虑枚举 \(0\) 入度的点集（必须为独立集），强制这个点集向外的边只能连出不能连入

• 这样无法保证外面的点入度不为 \(0\)，考虑容斥掉有多出 \(0\) 入度点的情况

• 省略推导过程，

• \[f_S=\sum_{T\subseteq S,T\text{ is an independent set}}(-1)^{|T|-1}f_{S-T} \]

• 设集合幂级数 \(g=\sum_{S\text{ is an independent set}}(-1)^{|S|-1}x^S\)，对 \(g\) 的占位多项式每一项求 FMT 之后就能推出 \(f\) 占位多项式的每一项的 FMT

• \(O(2^nn^2)\)

• 也可以从另一个角度理解：上式相当于 \(f=f\bigotimes g+1\)，也就是 \(f=\frac1{1-g}\)，上面推出 \(f\) 的某一项，本质上是在进行一个求逆的过程

• （此处为后话）

• 而 \(1-g\) 的第 \(T\) 项，若 \(T\) 为独立集（包括空集）则为 \((-1)^{|T|}\)，否则为 \(0\)

• 对于常数项为 \(1\) 的集合幂级数 \(A\)，有个性质是 \(A^k\)（子集卷积意义下）的每一项都是关于 \(k\) 的多项式（可以根据空集在 \(k\) 次中被选出的次数进行证明）

• 故我们得出一个结论：给图用 \(k\) 种颜色染色（边两端的点颜色不同）的方案数 \(f(k)\) 是一个关于 \(k\) 的多项式，给图定向成为 DAG 的方案数为 \((-1)^nf(-1)\)

LOJ#154 集合划分计数

• 给定一个集合幂级数 \(f\)，求把全集划分成不超过 \(k\) 个集合（集合之间无序），这些集合在 \(f\) 中对应项的乘积之和

• 这是一个不完整的 \(\exp\)：

• \[g=\sum_{i=0}^k\frac{f^i}{i!} \]

• 还是考虑和 \(\exp\) 一样求导：

• \[g‘=\sum_{i=1}^k\frac{if^{i-1}f‘}{i!}=f‘\sum_{i=0}^{k-1}\frac{f^i}{i!} \]

• 于是我们有：

• \[g‘=f‘(g-\frac{f^k}{k!}) \]

• 也可以从小到大推 \(g\) 占位多项式的每一项

• 参考 EI 的博客

[学习笔记]子集卷积

原文：https://www.cnblogs.com/xyz32768/p/12953188.html