前置知识

  • 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 的博客