[学习笔记]子集卷积

前置知识

FMT：对于两个下标在 ([0,2^n)) 的数组 (f) 和 (g)，求：
[h_i=sum_{j ext{ or }k=i}f_jg_k ]
可以做到 (O(2^nn))
~~限于博主水平，~~这里不放该前置算法的流程，请自行百度

引入

对于两个下标在 ([0,2^n)) 的数组 (f) 和 (g)，求：
[h_i=sum_{j ext{ and }k=varnothing,j ext{ or }k=i}f_jh_k ]
(j,k) 的条件即为集合 (j) 和 (k) 恰好拼成集合 (i)
(h) 为 (f) 和 (g) 的子集卷积
可以做到 (O(2^nn^2)) 的复杂度

算法流程

下面用 (|i|) 表示 (popcount(i))，即 (i) 二进制下 (1) 的个数
注意到 (j ext{ and }k=varnothing) 时必有 (|j|+|k|=|j ext{ or }k|)
故引入占位多项式：
[F_{i,j}=egin{cases}f_j & |j|=i\0 & |j| e iend{cases} ]
求 (H_{i,j}) 时，可以枚举拼成 (j) 的两个集合大小 (i_1) 和 (i_2)，我们有：
[H_{i,j}=sum_{i_1+i_2=i}sum_{a ext{ or }b}F_{i_1,a}G_{i_2,b} ]
也就是：
[H_i=sum_{i_1+i_2=i}F_{i_1}igotimes G_{i_2} ]
(igotimes) 为或卷积
(H_i) 中可能会有 (1) 的个数小于 (i) 的项为 (0)，但这并不重要
对于每个 (0le ile n)，把 (F_i) 和 (G_i) 做一遍 FMT，作一遍上式之后得到 (H) 再 IFMT 回来即可得到 (h)
(O(2^nn^2))

拓展

观察这个式子
[H_i=sum_{i_1+i_2=i}F_{i_1}igotimes 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) 边的有向图，可以将部分边反向，求使得原图无环的所有方案下，翻转的边数之和，(nle 18)
首先无环图所有边反向之后还是无环图，这样的两个合法图一一对应并且翻转的边数之和为 (m)，故答案为方案数乘 (frac m2)
(f_S) 表示点集 (S) 无环的方案数
一个图无环当且仅当这个图能够拓扑排序，严谨地说就是每次删掉图中入度为 (0) 的点集可以删完所有点
考虑枚举 (0) 入度的点集（必须为独立集），强制这个点集向外的边只能连出不能连入
这样无法保证外面的点入度不为 (0)，考虑容斥掉有多出 (0) 入度点的情况
省略推导过程，
[f_S=sum_{Tsubseteq S,T ext{ is an independent set}}(-1)^{|T|-1}f_{S-T} ]
设集合幂级数 (g=sum_{S ext{ is an independent set}}(-1)^{|S|-1}x^S)，对 (g) 的占位多项式每一项求 FMT 之后就能推出 (f) 占位多项式的每一项的 FMT
(O(2^nn^2))
也可以从另一个角度理解：上式相当于 (f=figotimes 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}^kfrac{f^i}{i!} ]
还是考虑和 (exp) 一样求导：
[g'=sum_{i=1}^kfrac{if^{i-1}f'}{i!}=f'sum_{i=0}^{k-1}frac{f^i}{i!} ]
于是我们有：
[g'=f'(g-frac{f^k}{k!}) ]
也可以从小到大推 (g) 占位多项式的每一项
参考 EI 的博客