Set Power Series

Posted on 2022-02-07 Edited on 2022-02-24 In notes

集合幂级数及其运算

对于实值函数 \(f:U\rightarrow R\), 定义集合幂级数\(F(z)=\sum_Sf(S)z^S\), 其中\(z^S\)满足\(z^S\cdot z^T=z^{S\cup T}\).

按位分治

for (int i = 1; i < N; i <<= 1)
  for (int j = 0; j < N; j += i * 2)
    for (int k = j; k < i + j; ++k)
      f[k+i] += f[k];

FMT 满足如下性质:

### IFMT (子集差分)

FMT 的逆运算

for (int i = 1; i < N; i <<= 1)
  for (int j = 0; j < N; j += i * 2)
    for (int k = j; k < i + j; ++k)
      f[k+i] -= f[k];

\(F_i(z)=[u^i]\sum_Sf(S)z^Su^{|S|}\)

\(H(z)=\sum_{S\cap T=\emptyset}[z^S]F(z)\cdot [z^T]G(z)z^{S\cup T}\)

注意集合不交的条件, 可以改成\(|S|+|T|=|S\cup T|\), 于是利用占位幂级数进行运算即可.

\[ \begin{aligned} H_k(z)&=\sum_{i+j=k}F_i(z)G_j(z)\\ FMT(H_k)&= \sum_{i+j=k}FMT(F_i)FMT(G_j)\ \end{aligned} \] 交换求和次序, 对\(FMT\)数组的每一项独立计算.

记\(f_S(z)=\sum_k [FMT(F_k)]_Sz^k\), 子集卷积实际上是 \(h_S(z)=f_S(z)g_S(z)\).

\(\exp\), \(\ln\), 求逆, 多项式复合等运算, 和刚才的分析同理. 对每一项占位多项式进行对应的操作即可.

note: exp将联通图转化为有多个联通分量的图, ln作为逆运算反之.

注意到\(O(n^2)\)递推的方向是集合大小不断增加, 下一层的值由前面层的答案组成, 天然支持在线.