[学习笔记]子集卷积

2023年4月7日下午9:43 • 卷积神经网络

前置知识

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)\)