集合幂级数

https://www.cnblogs.com/birchtree/p/14531986.html
https://www.luogu.me/article/vx00cltm
https://www.luogu.me/article/1p22g6n4

以下定义 \(z^S\cdot z^T=[S\cap T=\varnothing]z^{S\cup T}\)（无交并）。于是集合幂级数的乘法就定义为子集卷积。子集卷积显然具有交换律和结合律，其单位元为 \(z^{\varnothing}\)。如果 \([z^{\varnothing}]F\ne 0\)，那么其有唯一逆元。

集合无交并在图上具有良好的组合意义，因此可以解决许多图论计数问题。

子集卷积（乘法）

给定两个集合幂级数 \(F(z),G(z)\)，假设要计算 \(F(z)G(z)\)。发现我们常用的 Bitwise Or 卷积可能在 \(S\cap T\ne \varnothing\) 时产生贡献。注意到 \(S\cap T=\varnothing\) 当且仅当 \(|S\cup T|=|S|+|T|\)，于是开三组 \((n+1)\times 2^n\) 的二维数组 \(a[n],b[n],c[n]\)，把 \([z^S]F\to [z^S]a[\operatorname{cnt}(S)]\)，\([z^S]G\to [z^S]b[\operatorname{cnt}(S)]\)，然后对 \(2n+2\) 行分别做 fwt，然后对每列做卷积（\(i,j\to i+j\)，即 \(|S|,|T|\to |S+T|\)），再对每行 ifwt 回来，然后提取 \([z^S]c[\operatorname{cnt}(S)]\to[z^S]res\)。

代码

int a[N + 1][1 << N], b[N + 1][1 << N], c[N + 1][1 << N];
inline void conv(int f1[], int f2[], int g[]) {
    for(int i = 0; i <= n; i++)
        for(int j = 0; j < (1 << n); j++) a[i][j] = b[i][j] = c[i][j] = 0;
    for(int s = 0; s < (1 << n); s++) a[__builtin_popcount(s)][s] = f1[s], b[__builtin_popcount(s)][s] = f2[s];
    for(int i = 0; i <= n; i++) fwt(a[i]), fwt(b[i]);
    for(int i = 0; i <= n; i++) {
        for(int j = 0; i + j <= n; j++) {
            for(int s = 0; s < (1 << n); s++) {
                add(c[i + j][s], (ll)a[i][s] * b[j][s] % MOD);
            }
        }
    }
    for(int i = 0; i <= n; i++) ifwt(c[i]);
    for(int s = 0; s < (1 << n); s++) g[s] = c[__builtin_popcount(s)][s];
}

求逆

显然可以仿照形式幂级数进行递推，稍微观察发现只需对每一列分别求逆即可。

exp

对于集合幂级数 \(F(z)\)，定义

\[ \exp(F)=\sum_{i=0}^{+\infty}\frac{F^i}{i!} \]

显然在 \([z^{\varnothing}]F=0\) 时上式收敛。其有组合意义：\([z^S]\exp(F)\) 表示枚举 \(S\) 的无序划分，各部分的 \(F\) 的积的和。那么如何快速计算呢？记

\[ G_i=\sum_{S\subseteq U}[|S|=i]f_sz^S \]

那么考虑到

\[ \begin{align*} [z^S]\exp(F)&=\sum_{\{T_1,\cdots,T_k\}为S的有序划分}\frac{1}{k!}\prod_{j=1}^{k}[z^{T_j}]F\\ &=\sum_{x_1+x_2+\cdots+x_k=|S|为|S|的有序分拆}\frac{1}{k!}[z^S]\prod_{j=1}^{k}G_{x_j} \end{align*} \]

于是我们可以给 \(G_i\) 进行 fwt 之后，直接对每一列进行 \(\exp\)。这里可以直接用 \(O(n^2)\) 递推 \(\exp\)。