FWT & FMT & 集合幂级数学习笔记

_czy · 2026-04-14 21:06:59 · 算法·理论

集合幂级数

集合幂级数听起来很难，实则不难理解。简单来说，集合幂级数就是把一个全集的每个子集都映射到一个值。

那么集合幂级数具体如何表示的呢？我们考虑用一个类多项式表示，在全集 U 的每个子集 S 对应的值添加占位符 x^S。注意：这里的 x^S 无实际意义，仅仅只是一个占位符。

所以，集合幂级数 F(x) 可以表示为：

F(x)=\sum_{S\subseteq U}f_Sx^S

加减法

集合幂级数的加减法很简单，只要将对应系数相加减即可，形式化来说：

F(x)\pm G(x)=\sum_{S\subseteq U}(f_S\pm g_S)x^S

乘法

这个比较麻烦了，我们希望集合幂级数的乘法对加法有分配律。形式化来说就是要满足：

F(x)\ast G(x)=\sum_{L\subseteq U}f_Lx^L\sum_{R\subseteq U}g_Rx^R=\sum_{L\subseteq U}\sum_{R\subseteq U}f_Lg_Rx^{L\otimes R}=\sum_{S\subseteq U}\left(\sum_{L\otimes R=S}f_Lg_R\right)x^S

其中 \otimes 是集合间的一种二元运算，具有交换律，结合律，以及单位元。因此，集合幂级数的乘法类型有很多，常见的乘法类型有集合并卷积，集合交卷积，集合对称差卷积。如果将集合用二进制数表示，则它们分别对应了位运算卷积中的或卷积，与卷积，异或卷积。具体怎么快速计算将在接下来介绍。

引入

FFT 大家应该都了解过了，它们都是对于加法卷积的快速变换。同理，对于位运算卷积，也有对应的快速变换，那就是 FWT 和 FMT。

先来看位运算卷积的形式：

C_{k}=\sum_{i\otimes j=k}A_iB_j

其中 \otimes 是一种位运算，如果 \otimes 换成 + 就变成了加法卷积，就是多项式乘法。

我们希望这个 O(n^2) 的东西通过某些手段变成 O(n\log n) 的。可以发现，这与加法卷积类似，所以我们可以效仿 FFT 的方法，通过 O(n\log n) 的正变换，再用 O(n) 的点乘快速计算，最后用 O(n\log n) 的逆变换得到结果。

下文可能会将集合直接看作二进制数考虑，将集合间的运算直接看作位运算，请读者自行转化。由于一般情况下 n=2^m，所以下文 n 直接看作 2^m。

FWT

FWT 的应用场景更多，我认为更重要，所以先讲 FWT。

我们不妨设 FWT(f) 表示集合幂级数 f 经过 FWT 变换后的集合幂级数。

既然要转化成点乘的形式，那么 A\ast B=C\Leftrightarrow FWT(A)\cdot FWT(B)=FWT(C)。

由于 FFT 是一个线性变换，我们希望 FWT 也是一个线性变换，所以我们可以设 c(i,j) 表示贡献系数，形式化来说就是：

FWT(A)_i=\sum_{j=0}^{n-1}c(i,j)A_j

根据 FWT(A)\cdot FWT(B)=FWT(C) 可以得到：

FWT(A)_iFWT(B)_i=FWT(C)_i

\sum_{j=0}^{n-1}c(i,j)A_j\sum_{k=0}^{n-1}c(i,k)B_k=\sum_{p=0}^{n-1}c(i,p)C_p

\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k=\sum_{p=0}^{n-1}c(i,p)C_p

根据 A\ast B=C 可以得到：

C_p=\sum_{j\otimes k=p}A_jB_k

\sum_{p=0}^{n-1}c(i,p)C_p=\sum_{p=0}^{n-1}c(i,p)\sum_{j\otimes k=p}A_jB_k

\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k=\sum_{p=0}^{n-1}c(i,p)\sum_{j\otimes k=p}A_jB_k

\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k=\sum_{p=0}^{n-1}\sum_{j\otimes k=p}c(i,j\otimes k)A_jB_k

\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j)c(i,k)A_jB_k=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}c(i,j\otimes k)A_jB_k

注意到原式等价于 c(i,j)c(i,k)=c(i,j\otimes k)。

由于位运算的独立性，我们可以拆位考虑。假设我们已经知道了 c([0,1],[0,1])，不妨设二进制数 x 的每一位是 x_0,x_1,x_2,\cdots，显然 x_i\in\{0,1\}。

考虑构造 c(i,j)=c(i_0,j_0)c(i_1,j_1)c(i_2,j_2)\cdots，则 \forall t,c(i_t,j_t)c(i_t,k_t)=c(i_t,j_t\otimes k_t)\Rightarrow c(i,j)c(i,k)=c(i,j\otimes k)。所以这样构造是满足我们的条件的。

现在我们已经有了符合要求的 c，那么如何快速求解 FWT 变换呢？这时，我们又想起了 FFT，它们运用了分治的思想，FWT 是否也可以呢？答案是可以。

观察以下式子：

FWT(f)_i=\sum_{j=0}^{n-1}c(i,j)f_j

暴力求和显然是 O(n^2) 的，无法接受。

考虑像 FFT 一样分治，设 f_0 表示序列 f 中，下标二进制最高位的值为 0 组成的序列；f_1 表示序列 f 中，下标二进制最高位的值为 1 组成的序列。那么我们可以得到（其中 i' 表示 i 去掉二进制首位后的值）：

FWT(f)_i=\sum_{j=0}^{\frac{n}{2}-1}c(i,j)f_j+\sum_{j=\frac{n}{2}}^{n-1}c(i,j)f_j

FWT(f)_i=c(i_0,0)\sum_{j=0}^{\frac{n}{2}-1}c(i',j')f_j+c(i_0,1)\sum_{j=\frac{n}{2}}^{n-1}c(i',j')f_j

接下来，分类讨论 i 的首位是 0 还是 1（以下式子满足 i\in[0,\frac{n}{2})）：

FWT(f)_i=c(0,0)FWT(f_0)_i+c(0,1)FWT(f_1)_i

FWT(f)_{i+\frac{n}{2}}=c(1,0)FWT(f_0)_i+c(1,1)FWT(f_1)_i

所以，我们可以 O(n) 合并 f_0 和 f_1，则时间复杂度为 O(m2^m) 或者 O(n\log n)。IFWT同理，只要对 c 矩阵求逆即可，所以 c 矩阵要有逆，否则正变换后无法逆变换，一切运算均无意义。

以下我将分三种位运算具体讲解贡献系数 c([0,1],[0,1]) 是什么，分别是集合并卷积、集合交卷积、集合对称差卷积，构造过程较繁琐，可直接记结论。

构造原理就是根据 c(i,j)c(i,k)=c(i,j\otimes k) 构造出 c([0,1],[0,1]) 即可。

集合并卷积

最基本的式子：

c(i,j)c(i,k)=c(i,j\cup k)

逐步推导：

令 j=k，得 c(i,j)^2=c(i,j)，所以 c(i,j)\in\{0,1\}。
考虑 i=0 的情况：
- 令 j=0,k=1：c(0,0)c(0,1)=c(0,1)。
  - 若 c(0,1)=0，则等式成立。
  - 若 c(0,1)\neq0，则 c(0,0)=1。
考虑 i=1 的情况：
- 令 j=0,k=1：c(1,0)c(1,1)=c(1,1)。
  - 若 c(1,1)=0，则等式成立。
  - 若 c(1,1)\neq0，则 c(1,0)=1。
综合以上条件得到可行且可逆的矩阵：
- \begin{bmatrix}1&1\\1&0\end{bmatrix}

注意到对于矩阵 \begin{bmatrix}1&0\\1&1\end{bmatrix}，有 c(i,j)=[i\cup j=i] 即 [j\subseteq i]，所以 FWT(f)_i=\sum_{j\subseteq i}f_j，这是子集求和。

那么，利用矩阵 \begin{bmatrix}1&0\\1&1\end{bmatrix} 可以得到正变换的式子（以下式子 i\in[0,\frac{n}{2})）：

FWT(f)_i=FWT(f_0)_i

FWT(f)_{i+\frac{n}{2}}=FWT(f_0)_i+FWT(f_1)_i

对矩阵求逆，得到 \begin{bmatrix}1&0\\-1&1\end{bmatrix}，就可以得到逆变换的式子：

IFWT(f)_i=IFWT(f_0)_i

IFWT(f)_{i+\frac{n}{2}}=-IFWT(f_0)_i+IFWT(f_1)_i

:::info[代码]{open}

void FWTOR(ll*F){
    for(int l=1;l<n;l<<=1){
        for(int p=0;p<n;p+=l<<1){
            for(int i=p;i<p+l;i++){
                F[i+l]=(F[i]+F[i+l])%P;
            }
        }
    }
}
void IFWTOR(ll*F){
    for(int l=1;l<n;l<<=1){
        for(int p=0;p<n;p+=l<<1){
            for(int i=p;i<p+l;i++){
                F[i+l]=(P-F[i]+F[i+l])%P;
            }
        }
    }
}

:::

集合交卷积

最基本的式子：

c(i,j)c(i,k)=c(i,j\cap k)

逐步推导：

令 j=k，得 c(i,j)^2=c(i,j)，所以 c(i,j)\in\{0,1\}。
考虑 i=0 的情况：
- 令 j=0,k=1：c(0,0)c(0,1)=c(0,0)。
  - 若 c(0,0)=0，则等式成立。
  - 若 c(0,0)\neq0，则 c(0,1)=1。
考虑 i=1 的情况：
- 令 j=0,k=1：c(1,0)c(1,1)=c(1,0)。
  - 若 c(1,0)=0，则等式成立。
  - 若 c(1,0)\neq0，则 c(1,1)=1。
综合以上条件得到可行且可逆矩阵：
- \begin{bmatrix}0&1\\1&1\end{bmatrix}

注意到对于矩阵 \begin{bmatrix}1&1\\0&1\end{bmatrix}，有 c(i,j)=[i\cap j=i] 即 [i\subseteq j]，所以 FWT(f)_i=\sum_{i\subseteq j}f_j，这是超集求和。

那么，利用矩阵 \begin{bmatrix}1&1\\0&1\end{bmatrix} 可以得到正变换的式子（以下式子 i\in[0,\frac{n}{2})）：

FWT(f)_i=FWT(f_0)_i+FWT(f_1)_i

FWT(f)_{i+\frac{n}{2}}=FWT(f_1)_i

对矩阵求逆，得到 \begin{bmatrix}1&-1\\0&1\end{bmatrix}，就可以得到逆变换的式子：

IFWT(f)_i=IFWT(f_0)_i-IFWT(f_1)_i

IFWT(f)_{i+\frac{n}{2}}=IFWT(f_1)_i

:::info[代码]{open}

void FWTAND(ll*F){
    for(int l=1;l<n;l<<=1){
        for(int p=0;p<n;p+=l<<1){
            for(int i=p;i<p+l;i++){
                F[i]=(F[i]+F[i+l])%P;
            }
        }
    }
}
void IFWTAND(ll*F){
    for(int l=1;l<n;l<<=1){
        for(int p=0;p<n;p+=l<<1){
            for(int i=p;i<p+l;i++){
                F[i]=(F[i]+P-F[i+l])%P;
            }
        }
    }
}

:::

集合对称差卷积

最基本的式子：

c(i,j)c(i,k)=c(i,j\oplus k)

逐步推导：

考虑 j=k=0，得 c(i,0)^2=c(i,0)，所以 c(i,0)\in\{0,1\}。
- 如果 c(0,0)=0，取 k=0：c(0,j)c(0,0)=c(0,j)，得 0=c(0,j)，所以第一行全零，矩阵不可逆。
- 因此必须 c(0,0)=1。
考虑 i=0：
- 取 j=1,k=1：c(0,1)^2=c(0,0)=1，所以 c(0,1)\in\{-1,1\}。
考虑 i=1：
- 取 j=1,k=1：c(1,1)^2=c(1,0)。
- 取 j=0,k=1：c(1,0)c(1,1)=c(1,1)。
  - 如果 c(1,1)\neq0，则 c(1,0)=1。
  - 如果 c(1,1)=0，则由第一个式子得 c(1,0)=0，第二行全零，矩阵不可逆。
所以 c(1,1)=\pm1 且 c(1,0)=1。
综合以上条件得到可行且可逆矩阵：
- \begin{bmatrix}1&-1\\1&1\end{bmatrix}

注意到，在矩阵 \begin{bmatrix}1&1\\1&-1\end{bmatrix} 中，有 c(i,j)=(-1)^{|i\cap j|}。

那么，利用矩阵 \begin{bmatrix}1&1\\1&-1\end{bmatrix} 可以得到正变换的式子（以下式子 i\in[0,\frac{n}{2})）：

FWT(f)_i=FWT(f_0)_i+FWT(f_1)_i

FWT(f)_{i+\frac{n}{2}}=FWT(f_0)_i-FWT(f_1)_i

对矩阵求逆，得到 \begin{bmatrix}0.5&0.5\\0.5&-0.5\end{bmatrix}，就可以得到逆变换的式子：

IFWT(f)_i=\frac{IFWT(f_0)_i+IFWT(f_1)_i}{2}

IFWT(f)_{i+\frac{n}{2}}=\frac{IFWT(f_0)_i-IFWT(f_1)_i}{2}

:::info[代码]{open}

void FWTXOR(ll*F){
    for(int l=1;l<n;l<<=1){
        for(int p=0;p<n;p+=l<<1){
            for(int i=p;i<p+l;i++){
                ll x=F[i],y=F[i+l];
                F[i]=(x+y)%P,F[i+l]=(x-y)%P;
            }
        }
    }
}
void IFWTXOR(ll*F){
    FWTXOR(F);
    for(int i=0;i<n;i++)F[i]=F[i]*qpow(n,P-2);
}

:::

FMT

还是稍微提一下 FMT，FMT 是 FWT 在或卷积和与卷积下的一种特例，其变换矩阵是上/下三角的0/1矩阵，对应高维前缀/后缀和。个人认为通过构造的方式更容易理解 FMT，所以我将通过构造的角度讲解。

还是一样的设 FMT(f) 表示集合幂级数 f 经过 FMT 变换后的集合幂级数。

显然我们要想办法构造满足 A\ast B=C\Leftrightarrow FMT(A)\cdot FMT(B)=FMT(C)。

集合或卷积

注意到，如果 FMT(f)_i=\sum_{j\subseteq i}f_j，则可以满足条件，以下是证明：

FMT(A)_iFMT(B)_i=\sum_{j\subseteq i}A_j\sum_{k\subseteq i}B_k

FMT(A)_iFMT(B)_i=\sum_{j\subseteq i}\sum_{k\subseteq i}A_jB_k

FMT(A)_iFMT(B)_i=\sum_{p\subseteq i}\sum_{j\cup k=p}A_jB_k

根据 A\ast B=C 可以得到：

C_p=\sum_{j\cup k=p}A_jB_k

简单代换得到：

FMT(A)_iFMT(B)_i=\sum_{p\subseteq i}C_p

FMT(A)_iFMT(B)_i=FMT(C)_i

所以，我们成功证明了 A\ast B=C\Leftrightarrow FMT(A)\cdot FMT(B)=FMT(C)。

显然正变换就是高维前缀和，逆变换就是高维差分，实现利用 SOS DP 即可，则时间复杂度为 O(m2^m) 或者 O(n\log n)。

:::info[代码]{open}

void FMTOR(ll*F){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(j&(1<<i))F[j]=(F[j]+F[j-(1<<i)])%P;
        }
    }
}
void IFMTOR(ll*F){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(j&(1<<i))F[j]=(F[j]-F[j-(1<<i)])%P;
        }
    }
}

:::

集合交卷积

注意到，如果 FMT(f)_i=\sum_{i\subseteq j}f_j，则可以满足条件，以下是证明：

FMT(A)_iFMT(B)_i=\sum_{j\supseteq i}A_j\sum_{k\supseteq i}B_k

FMT(A)_iFMT(B)_i=\sum_{j\supseteq i}\sum_{k\supseteq i}A_jB_k

FMT(A)_iFMT(B)_i=\sum_{p\supseteq i}\sum_{j\cap k=p}A_jB_k

根据 A\ast B=C 可以得到：

C_p=\sum_{j\cap k=p}A_jB_k

简单代换得到：

FMT(A)_iFMT(B)_i=\sum_{i\subseteq p}C_p

FMT(A)_iFMT(B)_i=FMT(C)_i

所以，我们成功证明了 A\ast B=C\Leftrightarrow FMT(A)\cdot FMT(B)=FMT(C)。

显然正变换就是高维后缀和，逆变换就是高维差分，实现利用 SOS DP 即可，则时间复杂度为 O(m2^m) 或者 O(n\log n)。

:::info[代码]{open}

void FMTAND(ll*F){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(j&(1<<i))F[j-(1<<i)]=(F[j-(1<<i)]+F[j])%P;
        }
    }
}
void IFMTAND(ll*F){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(j&(1<<i))F[j-(1<<i)]=(F[j-(1<<i)]-F[j])%P;
        }
    }
}

:::

例题

注：为了方便，以下一般记 f_S=[x^S]F(x),g_S=[x^S]G(x)。

P4717

模板题，使用 FWT/FMT 即可，但是对称差卷积只能用 FWT。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1<<17,P=998244353,I=499122177,
Cor[2][2]  ={{1,0},{1,1}},
Cand[2][2] ={{1,1},{0,1}},
Cxor[2][2] ={{1,1},{1,P-1}},
ICor[2][2] ={{1,0},{P-1,1}},
ICand[2][2]={{1,P-1},{0,1}},
ICxor[2][2]={{I,I},{I,P-I}};
int n,a[N],b[N];
ll F[N],G[N];
void FWT(ll*F,const int c[2][2]){
    for(int l=1;l<n;l<<=1){
        for(int p=0;p<n;p+=l<<1){
            for(int i=p;i<p+l;i++){
                ll t0=F[i],t1=F[i+l];
                F[i]=(c[0][0]*t0+c[0][1]*t1)%P;
                F[i+l]=(c[1][0]*t0+c[1][1]*t1)%P;
            }
        }
    }
}
void mul(ll*F,ll*G,const int C[2][2],const int IC[2][2]){
    FWT(F,C),FWT(G,C);
    for (int i=0;i<n;i++)F[i]=F[i]*G[i]%P;
    FWT(F,IC);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    n=1<<n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=0;i<n;i++)F[i]=a[i],G[i]=b[i];
    mul(F,G,Cor,ICor);
    for(int i=0;i<n;i++){
        cout<<F[i]<<' ';
        F[i]=a[i],G[i]=b[i];
    }
    cout<<'\n';
    mul(F,G,Cand,ICand);
    for(int i=0;i<n;i++){
        cout<<F[i]<<' ';
        F[i]=a[i],G[i]=b[i];
    }
    cout<<'\n';
    mul(F,G,Cxor,ICxor);
    for(int i=0;i<n;i++)cout<<F[i]<<' ';
}

:::

P6097

子集卷积的模板题，挺重要的，需要使用一个套路。

注意到有两个限制，限制 i|j=k 直接进行 FWT/FMT，限制 i\&j=0 可转化为 |i|+|j|=|i|j|，所以我们可以再开一维记录集合中的元素个数，转移的时候记录一下即可，详见代码。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1<<20,P=1e9+9;
int n,m,a[21][N],b[21][N],c[21][N];
int gt(int x){return __builtin_popcount(x);}
void fwt(int*f,int op){
    for(int l=1;l<m;l<<=1){
        for(int p=0;p<m;p+=l<<1){
            for(int i=p;i<p+l;i++){
                f[i+l]=(f[i]*op+f[i+l])%P;
            }
        }
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    m=1<<n;
    for(int i=0;i<m;i++)cin>>a[gt(i)][i];
    for(int i=0;i<m;i++)cin>>b[gt(i)][i];
    for(int i=0;i<=n;i++)fwt(a[i],1),fwt(b[i],1);
    for(int i=0;i<=n;i++){
        for(int j=0;i+j<=n;j++){
            for(int k=0;k<m;k++){
                c[i+j][k]=(c[i+j][k]+1ll*a[i][k]*b[j][k])%P;
            }
        }
    }
    for(int i=0;i<=n;i++)fwt(c[i],-1);
    for(int i=0;i<m;i++)cout<<(c[gt(i)][i]+P)%P<<' ';
}

:::

AT_arc100_c

直接算 \max_{\substack{i|j\le k\\i\neq j}}a_i+a_j 无法入手，因为 i|j\le k 不知道怎么处理。

考虑把答案转化为前缀和的形式，先算 \max_{\substack{i|j\subseteq k\\i\neq j}}a_i+a_j 的值，再前缀和即可。

但是该式如何计算？发现就是高维前缀和的最大值和次大值，在模板基础上多维护一个值即可。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
const int N=1<<18;
int n,s;
pi f[N];
void mx(pi&x,pi y){
    if(x.first<y.first)x={y.first,max(x.first,y.second)};
    else x={x.first,max(x.second,y.first)};
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    n=1<<n;
    for(int i=0;i<n;i++)cin>>f[i].first;
    for(int l=1;l<n;l<<=1)for(int p=0;p<n;p+=l<<1)for(int i=p;i<p+l;i++)mx(f[i+l],f[i]);
    s=f[0].first;
    for(int i=1;i<n;i++)cout<<(s=max(s,f[i].first+f[i].second))<<'\n';
}

:::

CF449D

直接算按位与为 0 的序列数是困难的，考虑先算按位与为 S 的超集的数量为 f_S，再通过高维差分得到按位与为 S 的数量为 g_S，答案即为 g_0。

但是如何计算 f_S 的值呢？显然对于 a_i\supseteq S，a_i 可选可不选，否则一定不能选。记 c_S 表示满足 a_i\supseteq S 的数量，则 f_S=2^{c_S}，c_S 直接用高维后缀和计算即可。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1<<20,P=1e9+7;
int n,m=1<<20,x;
ll f[N];
ll qpow(ll a,int b){
    ll s=1;
    while(b){
        if(b%2)s=s*a%P;
        a=a*a%P,b/=2;
    }
    return s;
}
inline void fwt(ll*f,ll op){
    for(int l=1;l<m;l<<=1){
        for(int p=0;p<m;p+=l<<1){
            for(int i=p;i<p+l;i++){
                f[i]=(f[i]+f[i+l]*op)%P;
            }
        }
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        f[x]++;
    }
    fwt(f,1);
    for(int i=0;i<m;i++)f[i]=qpow(2,f[i]);
    fwt(f,-1);
    cout<<(f[0]+P)%P;
}

:::

P12232

集合幂级数求逆的模板。

由于 F(x)G(x)=1：

\sum_{S\subseteq U}x^S(\sum_{\substack{P\cup Q=S\\P\cap Q=\varnothing}}f_Pg_Q)=f_\varnothing g_\varnothing+\sum_{\substack{S\subseteq U\\S\neq \varnothing}}x^S(\sum_{\substack{P\cup Q=S\\P\cap Q=\varnothing}}f_Pg_Q)=1

显然，g_\varnothing=\frac{1}{f_\varnothing}，否则：

g_S=-\frac{1}{f_\varnothing}\sum_{\substack{P\cup Q=S\\P\cap Q=\varnothing\\P\neq\varnothing}}f_Pg_Q(S\neq\varnothing)

直接做子集卷积即可，详见代码。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define gt __builtin_popcount
#define ll long long
const int N=1<<20,P=998244353;
int n,m,t,a[N],F[21][N],G[21][N];
ll qpow(ll a,int b){
    ll s=1;
    while(b){
        if(b&1)s=s*a%P;
        a=a*a%P,b/=2; 
    }
    return s;
}
inline void fwt(int*f,int op){
    for(int l=1;l<m;l<<=1){
        for(int p=0;p<m;p+=l<<1){
            for(int i=p;i<p+l;i++){
                f[i+l]=(f[i]*op+f[i+l])%P;
            }
        }
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    m=1<<n;
    for(int i=0;i<m;i++){
        cin>>a[i];
        F[gt(i)][i]=a[i];
    }
    for(int i=0;i<=n;i++)fwt(F[i],1);
    G[0][0]=t=qpow(a[0],P-2);
    fwt(G[0],1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            for(int s=0;s<m;s++){
                G[i][s]=(G[i][s]-1ll*F[i-j][s]*G[j][s])%P;
            }
        }
        for(int s=0;s<m;s++)G[i][s]=1ll*G[i][s]*t%P;
    }
    for(int i=0;i<=n;i++)fwt(G[i],-1);
    for(int i=0;i<m;i++)cout<<(G[gt(i)][i]+P)%P<<' ';
}

:::

P13843

集合幂级数 exp 的模板，素数版本可直接套用非素数模数版本。

考虑泰勒展开得到 \exp(F(x))=\sum_{k=0}^{+\infty}\frac{F(x)^k}{k!}。

考虑组合意义，\frac{[x^S]F(x)^k}{k!} 的意义是把 S 无序划分为 k 个集合的方案数，划分出的集合 T 内部的方案数是 f_T。

尝试 DP，记 f_S 表示集合 S 内部的方案数，设 g_S 表示 S 做无序划分的方案数，转移时枚举 \min(S) 所在集合 T：

g_S=f_S+\sum_{\substack{T\subsetneq S,T\neq\varnothing\\\min(T)=\min(S)}}f_Tg_{S-T}

实现的时候保证 \min(T)=\min(S) 后进行子集卷积即可，可参考如下代码。

:::info[代码]{open}

m=1<<n;
for(int k=0;k<=n;k++){
    for(int i=0;i<n;i++){
        for(int s=0;s<m;s++){
            if((s&1<<i)&&(s&-s)!=(1<<i))F[k][s]+=F[k][s^1<<i];
        }
    }
}

:::

以上代码可看作将 S 按 \min(S) 分层进行转移，保证了 \min(T)=\min(S)。

以下是完整代码：

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define gt __builtin_popcount
const int N=1<<20;
int n,m;
ll f[N],g[N],F[21][N],G[N],H[21][N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    m=1<<n;
    for(int i=0;i<m;i++){
        cin>>f[i];
        F[gt(i)][i]=f[i];
    }
    for(int k=0;k<=n;k++){
        for(int i=0;i<n;i++){
            for(int s=0;s<m;s++){
                if((s&1<<i)&&(s&-s)!=(1<<i))F[k][s]+=F[k][s^1<<i];
            }
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=0;i<n;i++){
            for(int s=0;s<m;s++){
                if((s&1<<i)&&(s&-s)!=(1<<i))H[k][s]-=H[k][s^1<<i];
            }
        }
        for(int s=0;s<m;s++){
            G[s]=0;
            if(gt(s)==k)G[s]=g[s]=f[s]+H[k][s];
        }
        for(int i=0;i<n;i++){
            for(int s=0;s<m;s++){
                if(s&1<<i)G[s]+=G[s^1<<i];
            }
        }
        for(int j=0;j+k<=n;j++)for(int s=0;s<m;s++)H[j+k][s]+=G[s]*F[j][s];
    }
    g[0]=1;
    for(int i=0;i<m;i++)cout<<g[i]<<' ';
}

:::

P13844

集合幂级数 ln 的模板，素数版本可直接套用非素数模数版本。

ln 运算是 exp 运算的逆运算，可以记 f_S 表示 S 做无序划分的方案数，设 g_S 表示集合 S 内部的方案数，就有：

g_S=f_S-\sum_{\substack{T\subsetneq S,T\neq\varnothing\\\min(T)=\min(S)}}f_{S-T}g_T

实现是类似的，以下是完整代码：

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define gt __builtin_popcount
const int N=1<<20;
int n,m;
ll f[N],g[N],h[N],F[21][N],G[N],H[21][N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    m=1<<n;
    for(int i=0;i<m;i++){
        cin>>f[i];
        F[gt(i)][i]=f[i];
    }
    for(int k=0;k<=n;k++){
        for(int i=0;i<n;i++){
            for(int s=0;s<m;s++){
                if(s&1<<i)F[k][s]+=F[k][s^1<<i];
            }
        }
    }
    for(int k=1;k<=n;k++){
        for(int s=0;s<m;s++)h[s]=H[k][s];
        for(int i=0;i<n;i++){
            for(int s=0;s<m;s++){
                if((s&1<<i)&&(s&-s)!=(1<<i))h[s]-=h[s^1<<i];
            }
        }
        for(int s=0;s<m;s++){
            G[s]=0;
            if(gt(s)==k)G[s]=g[s]=f[s]-h[s];
        }
        for(int i=0;i<n;i++){
            for(int s=0;s<m;s++){
                if((s&1<<i)&&(s&-s)!=(1<<i))G[s]+=G[s^1<<i];
            }
        }
        for(int j=0;j+k<=n;j++)for(int s=0;s<m;s++)H[j+k][s]+=G[s]*F[j][s];
    }
    for(int i=0;i<m;i++)cout<<g[i]<<' ';
}

:::

P11734

比较模板的图计数，做图计数之前需要先知道一个基本式子：

F=\exp G

其中 [x^S]F(x) 表示点集为 S 的生成子图个数，[x^S]G(x) 表示点集为 S 的联通生成子图个数，证明可考虑 \exp 的组合意义。

而本题中 F 是好求的，则 G=\ln F，就把题目转化为求 \sum_{k=1}^{+\infty}G^k 即 \frac{1}{1-G}，直接求逆即可。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define gt __builtin_popcount
const int N=1<<20,P=998244353;
int n,m,x,y,a[N],b[N],F[21][N],G[21][N],H[N],t;
int qpow(ll a,int b){
    ll s=1;
    while(b){
        if(b%2)s=s*a%P;
        a=a*a%P,b/=2;
    }
    return s;
}
void fmt0(int*f,int op){for(int i=0;i<n;i++)for(int s=0;s<m;s++)if(s&1<<i)(f[s]+=op*f[s^1<<i])%=P;}
void fmt1(int*f,int op){for(int i=0;i<n;i++)for(int s=0;s<m;s++)if((s&1<<i)&&(s&-s)!=(1<<i))(f[s]+=op*f[s^1<<i])%=P;}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        a[(1<<x-1)|(1<<y-1)]++;
    }
    m=1<<n;
    fmt0(a,1);
    for(int s=0;s<m;s++)a[s]=F[gt(s)][s]=qpow(2,a[s]);
    for(int k=0;k<=n;k++)fmt0(F[k],1);
    for(int k=1;k<=n;k++){
        fmt1(G[k],-1);
        for(int s=0;s<m;s++){
            H[s]=0;
            if(gt(s)==k)H[s]=b[s]=(a[s]-G[k][s])%P;
        }
        fmt1(H,1);
        for(int j=0;j+k<=n;j++)for(int s=0;s<m;s++)G[j+k][s]=(G[j+k][s]+(ll)H[s]*F[j][s])%P;
    }
    memset(F,0,sizeof F),memset(G,0,sizeof G);
    b[0]--;
    for(int s=0;s<m;s++)F[gt(s)][s]=b[s]=-b[s];
    for(int k=0;k<=n;k++)fmt0(F[k],1);
    t=qpow(b[0],P-2);
    for(int s=0;s<m;s++)G[0][s]=t;
    for(int k=1;k<=n;k++){
        for(int i=0;i<k;i++)for(int s=0;s<m;s++)G[k][s]=(G[k][s]-(ll)F[k-i][s]*G[i][s])%P;
        for(int s=0;s<m;s++)G[k][s]=(ll)G[k][s]*t%P;
    }
    fmt0(G[n],-1);
    cout<<(G[n][m-1]+P)%P;
}

:::