集合幂级数简记
stripe_python
·
2026-07-20 17:22:35
·
算法·理论
记号 & 约定
记 U 为全集，不加说明时 U=\{1,2,\cdots,n\} 。2^U 为 U 的全体子集。
设 f: 2^U \to \mathbb{R} ，定义集合幂级数 F(x)=\sum \limits_{S \subseteq U} f_S x^S ，其中 x 是形式元。
在 OI 中，视 f: 2^U \to \mathbb{Z}_p ，其中 p 是大质数。
将 F(x) 的 x^S 项系数记作 [x^S]F(x) 或 f_S 。
高维前缀和 / FMT
问题 1 给定 F ，求 G 满足 g_S=\sum\limits_{T \subseteq S} f_T 。
将集合视作 n 维空间中的 2^n 个点，S 的第 i 维坐标为 [i \in S] ，权值为 f_S 。则 g_S 是对某个子空间求权值和，因而这个问题被形象地称作高维前缀和。
对于高维前缀和问题，一般采取逐维前缀和的方法。我们以任意顺序枚举第 i 维，若 i \in S 则将 g_{S \setminus \{i\}} 贡献到 g_S 。对 n 个维度都做完前缀和后 G 即为所求，复杂度 O(n2^n) 。
for (int i = 0; i < n; i++)
for (int s = 0; s < (1 << n); s++)
if (s >> i & 1) a[s] += a[s ^ (1 << i)];问题 2 给定 F ，求 G 满足 g_S=\sum\limits_{S \subseteq T} f_T 。
这是问题 1 的超集和版本，可以称作高维后缀和。只要改变贡献方向，令 g_S 贡献到 g_{S \setminus \{i\}} 即可。
问题 3 给定 G ，求 F 满足 g_S=\sum\limits_{T \subseteq S} f_T 。
这是问题 1 的逆变换，可以称作高维前缀差分。贡献时令 g_{S} 减去 g_{S \setminus \{i\}} 即可。
并 / 交 / 对称差卷积
集合幂级数的加法是平凡的对位相加：
F\pm G=\sum_{S \subseteq U}(f_S\pm g_S)x^S
对集合幂级数 F,G ，设 \oplus 是对 2^U 封闭的二元运算，则 F 与 G 的 \oplus 卷积为
F \times G=\sum_{W \subseteq U} \left(\sum_{S \oplus T=W} f_S g_T\right) x^W
当 \oplus 为并 / 交 / 对称差时，分别得到并卷积 / 交卷积 / 对称差卷积。由于常用二进制状压来表示集合，因此也可以称作 OR 卷积 / AND 卷积 / XOR 卷积。
处理这三类卷积的原则是，构造一个变换 \text{T} ，使得 \text{T}(F) \cdot \text{T} (G)=\text{T}(F \times G) ，其中 \cdot 表示点积，即系数的对位乘法。变换 \text{T} 的本质是用一组权重对系数进行线性组合。
设 \phi(S,T) 是 f_S 对 [x^T] \text{T}(F) 的贡献系数，则
\begin{aligned}
\text{T} (F)&=\sum_{T \subseteq U} \left(\sum _{S \subseteq U} \phi(S,T)f_S\right) x^T\\
\end{aligned}
记 H=F \times G 。我们希望 \forall T \subseteq U,[x^T]\text{T}(F) \times [x^T]\text{T} (G)=[x^T]\text{T}(H) 。代入得
\begin{aligned}
\left(\sum _{A \subseteq U} \phi(A,T)f_A\right)\left(\sum _{B \subseteq U} \phi(B,T)g_B\right)&=\sum _{C \subseteq U} \phi(C,T)h_C\\
\sum _{A \subseteq U} \sum _{B \subseteq U} \phi(A,T)\phi(B,T) f_A g_B&=\sum _{C \subseteq U} \phi(C,T)\sum_{A \oplus B=C} f_A g_B\\
\sum _{A \subseteq U} \sum _{B \subseteq U} \phi(A,T)\phi(B,T) f_A g_B&=\sum _{A \subseteq U} \sum _{B \subseteq U} \phi(A \oplus B,T) f_A g_B
\end{aligned}
称 \phi 为变换的特征函数。对比系数得 \phi 应当满足的条件：
问题 4 给定 F,G ，求 H 满足 h_W=\sum \limits_{S \cup T=W} f_Sg_T 。
这是并卷积 / OR 卷积 。给出构造 \phi(S,T)=[S \subseteq T] 。
:::::success[证明]
只要证
\begin{aligned}
\phi(S,W) \phi(T,W)&=\phi(S\cup T, W)\\
[S \subseteq W][T \subseteq W]&=[(S \cup T) \subseteq W]\\
[S \subseteq W][T \subseteq W]&=[S \subseteq W \land T \subseteq W]
\end{aligned}
显然成立，证毕。
:::::
考察 \text{T} 的实际意义
[x^W]\text{T}(F)=\sum_{S \subseteq U} [S \subseteq W] f_S
可以发现 \text{T}(F) 恰为 F 的高维前缀和。称变换 \text{T} 为 \text{FMT} ，并卷积做到 O(n2^n) 。
void fwt_or(mint *a, int n, int op) {
for (int i = 0; i < n; i++)
for (int s = 0; s < (1 << n); s++)
if (s >> i & 1) a[s] += a[s ^ (1 << i)] * op;
}对二元情形进行推广，可以得到 \text{FMT} 满足的性质
[x^S]\text{FMT} \left(\prod_{i=1}^k F_i\right)=\prod_{i=1}^k [x^S]\text{FMT}(F_i)
其中，F_i 的乘法是并卷积。
问题 5 给定 F,G ，求 H 满足 h_W=\sum \limits_{S \cap T=W} f_Sg_T 。
这是交卷积 / AND 卷积 。给出构造 \phi(S,T)=[T \subseteq S] 。
证明略去。此时 \text{T} 的实际意义变为高维后缀和，交卷积做到 O(n2^n) 。
void fwt_and(mint *a, int n, int op) {
for (int i = 0; i < n; i++)
for (int s = 0; s < (1 << n); s++)
if (s >> i & 1) a[s ^ (1 << i)] += a[s] * op;
}问题 6 给定 F,G ，求 H 满足 h_W=\sum \limits_{S \triangle T=W} f_Sg_T 。
这是对称差卷积 / XOR 卷积 。给出构造 \phi(S,T)=(-1)^{|S \cap T|} 。
:::::success[证明]
只要证
\begin{aligned}
\phi(S,W) \phi(T,W)&=\phi(S\Delta T, W)\\
(-1)^{|S \cap W|} (-1)^{|T \cap W|} &= (-1)^{|(S \Delta T) \cap W|}\\
(-1)^{|S \cap W|+|T \cap W|} &= (-1)^{|(S \Delta T) \cap W|}\\
|S \cap W|+|T \cap W| &\equiv |(S \Delta T) \cap W| \pmod 2
\end{aligned}
左式：注意到 |A|+|B|=|A \cup B|+|A \cap B| ，从而 |S \cap W|+|T \cap W|=|(S \cap W) \cup (T \cap W)|+|(S \cap W) \cap (T \cap W)|=|(S \cup T) \cap W|+|(S \cap T) \cap W| 。
右式：因为 S \triangle T=(S \cup T) \setminus (S \cap T) ，从而 |(S \triangle T) \cap W| =|(S \cup T) \cap W|-|(S \cap T) \cap W| 。
两式作差
\left(|(S \cup T) \cap W|+|(S \cap T) \cap W|\right)-\left(|(S \cup T) \cap W|-|(S \cap T) \cap W|\right)=2|(S \cap T) \cap W| \equiv 0 \pmod 2
故两式对 2 同余，证毕。
:::::
考察 \text{T} 的实际意义
[x^S]\text{T}(F)=\sum_{T \subseteq U} (-1)^{|S\cap T|} f_T
称变换 \text{T} 为 \text{FWT} 。关于 FWT 的计算，我们在下文说明。
线性代数观点
我们发现 \text{T} 是一个线性变换，考虑使用矩阵描述。对于二进制 FWT，设位矩阵
\begin{bmatrix}
\phi(0,0) & \phi(0,1) \\
\phi(1,0) & \phi(1,1)
\end{bmatrix}
| 卷积 | 位矩阵 | 逆矩阵 |
| :--------: | :------------------------------------------: | :--------------------------------------------------: |
| 并卷积 | $\begin{bmatrix}1 & 0 \\1 & 1\end{bmatrix}$ | $\begin{bmatrix}1 & 0 \\-1 & 1\end{bmatrix}$ |
| 交卷积 | $\begin{bmatrix}1 & 1 \\0 & 1\end{bmatrix}$ | $\begin{bmatrix}1 & -1 \\0 & 1\end{bmatrix}$ |
| 对称差卷积 | $\begin{bmatrix}1 & 1 \\1 & -1\end{bmatrix}$ | $\begin{bmatrix}0.5 & 0.5 \\0.5 & -0.5\end{bmatrix}$ |
从这个视角，可以自然地得到 FWT 的**线性性**
$$
\text{FWT}(aF+bG)=a \text{FWT}(F)+b\text{FWT}(G)
$$
## 分治乘法
类比 Karatsuba 做多项式卷积，我们尝试用分治处理集合幂级数的操作。
**问题 1** 给定 $F$，求 $G$ 满足 $g_S=\sum\limits_{T \subseteq S} f_T$。
钦定一个特殊元素 $z \in U$，设
$$
\begin{aligned}
F_0(x)&=\sum _{S \subseteq U, \textcolor{red}{z \notin S}} f_S x^S\\
F_1(x)&=\sum _{S \subseteq U, \textcolor{red}{z \in S}} f_S x^S
\end{aligned}
$$
将全集改为 $U \setminus \{x\}$，对 $F_0,F_1$ 递归求得其 FMT 结果 $G_0,G_1$。对 $g_S$ 进行讨论：
- 若 $z \notin S$，则 $g_S=[x^S] G_0$。
- 若 $z \in S$，则 $g_S=[x^{S \setminus \{z\}}] G_0+[x^{S \setminus \{z\}}]G_1$。
如果将子问题写作 $\text{FMT}(F_0,F_1)$，则递归过程视作
$$
\text{FMT}(F_0,F_1)=(\text{FMT}(F_0),\text{FMT}(F_0)+\text{FMT}(F_1))
$$
记 $m=2^n$，由递归式 $T(m)=2T\left(\dfrac{m}{2}\right)+O(m)$ 得 $T(m)=O(m \log m)$，从而复杂度 $O(n2^n)$。
至此，我们用分治解决了 FMT。从几何视角来看，每轮递归相当于一次降维，将空间划分为两个半空间解决问题。
**问题 4** 给定 $F,G$，求 $H$ 满足 $h_W=\sum \limits_{S \cup T=W} f_Sg_T$。
钦定一个特殊元素 $z \in U$，根据 $z \in S$ 是否成立，将 $F,G$ 划分为 $F_0,F_1,G_0,G_1$。则
$$
(F_0,F_1) \times (G_0,G_1)=(F_0 \times G_0, F_0 \times G_1 + F_1 \times G_0+F_1 \times G_1)
$$
直接递归需要四次卷积，由 $T(m)=4T\left(\dfrac{m}{2}\right)+O(m)$ 得 $T(m)=O(m^2)$，这不好。
注意到
$$
(F_0+F_1) \times (G_0+G_1)-F_0 \times G_0=F_0 \times G_1 + F_1 \times G_0+F_1 \times G_1
$$
转而计算 $F_0 \times G_0$ 和 $(F_0+F_1) \times (G_0+G_1)$，两次卷积，复杂度 $O(n2^n)$。
问题 1 和问题 4 的本质是对二元组 $(a,b)$ 施加变换 $(a,b) \to (a,a+b)$。由于 $a$ 是不含 $x$ 的结果，$b$ 是含 $x$ 的结果，上述变换等价于高维前缀和。这也从另一个角度说明了 FMT 的正确性。
**问题 6** 给定 $F,G$，求 $H$ 满足 $h_W=\sum \limits_{S \triangle T=W} f_Sg_T$。
钦定一个特殊元素 $z \in U$，根据 $z \in S$ 是否成立，将 $F,G$ 划分为 $F_0,F_1,G_0,G_1$。则
$$
(F_0,F_1) \times (G_0,G_1)=(F_0 \times G_0+F_1 \times G_1, F_0 \times G_1 + F_1 \times G_0)
$$
对二元组 $(a,b)$ 施加变换 $(a,b) \to (a+b,a-b)$。记
$$
\begin{aligned}
X&=(F_0+F_1) \times (G_0+G_1)\\
&=F_0 \times G_0+F_1 \times G_1+ F_0 \times G_1 + F_1 \times G_0\\
Y&=(F_0-F_1)\times(G_0-G_1)\\
&=F_0 \times G_0+F_1 \times G_1- F_0 \times G_1 - F_1 \times G_0
\end{aligned}
$$
解方程组得
$$
\begin{aligned}
F_0 \times G_0+F_1 \times G_1&= \dfrac{X+Y}{2}\\
F_0 \times G_1 - F_1 \times G_0&= \dfrac{X-Y}{2}\\
\end{aligned}
$$
计算 $X,Y$ 只要两次卷积。复杂度 $O(n2^n)$。
考虑将递归转为迭代，从而得到 FWT 实现对称差卷积的做法。
- FWT 正变换为 $(a,b) \to (a+b,a-b)$。
- FWT 逆变换为 $(a,b) \to \left(\dfrac{a+b}{2},\dfrac{a-b}{2}\right)$。
只要写出 $(a,b) \to (a+b,a-b) $ 的代码，逆变换在最后除以 $2^n$ 即可。
```cpp line-numbers
void fwt_xor(mint *a, int n, int op) {
for (int p = 1; p < (1 << n); p <<= 1)
for (int i = 0; i < (1 << n); i += (p << 1))
for (int j = 0; j < p; j++) {
mint x = a[i + j], y = a[i + j + p];
a[i + j] = x + y, a[i + j + p] = x - y;
}
if (op == 1) return;
mint inv = ~mint(1 << n);
for (int s = 0; s < (1 << n); s++) a[s] *= inv;
}
```
## $k$ 进制 FWT
考察 OR / AND / XOR 卷积的本质，将二进制数推广到 $k$ 进制：
- OR 推广到对位取 $\max$。
- AND 推广到对位取 $\min$。
- XOR 推广到不进位加法，即每一位加起来对 $k$ 取模。
我们仍考虑构造特征函数 $\phi$ 使得 $\phi(i,x) \phi(j,x) =\phi(i \oplus j, x)$。
**问题 7** 给定长为 $k^n$ 的数组 $a_0 \sim a_{k^n-1},b_{0} \sim b_{k^n-1}$，求数组 $c_i$ 满足 $c_x=\sum \limits_{x = i \oplus j} a_ib_j$，$\oplus$ 为 $k$ 进制下对位取 $\max$。
构造 $\phi(i,j)=[i \ge j]$，逆变换为
$$
\phi^{-1}(i,j)=\begin{cases}
1 \quad& i = j\\
-1 \quad& i = j + 1\\
0 \quad& i\ne j \land i\ne j+1
\end{cases}
$$
:::::success[证明]
只要证
$$
\begin{aligned}
\phi(i,x) \phi(j,x) &=\phi(i \oplus j, x)\\
[i \ge x][j \ge x] &=[(i \oplus j) \ge x]
\end{aligned}
$$
对 $i \oplus j$ 拆位易证 $(i \oplus j) \ge x$ 的充要条件是 $i \ge x\land j \ge x$，证毕。
:::::
**问题 8** 给定长为 $k^n$ 的数组 $a_0 \sim a_{k^n-1},b_{0} \sim b_{k^n-1}$，求数组 $c_i$ 满足 $c_x=\sum \limits_{x = i \oplus j} a_ib_j$，$\oplus$ 为 $k$ 进制下对位取 $\min$。
构造 $\phi(i,j)=[i\le j]$ 即可。逆变换和证明同理，不再叙述。
**问题 9** 给定长为 $k^n$ 的数组 $a_0 \sim a_{k^n-1},b_{0} \sim b_{k^n-1}$，求数组 $c_i$ 满足 $c_x=\sum \limits_{x = i \oplus j} a_ib_j$，$\oplus$ 为 $k$ 进制下不进位加法。
构造 $\phi(i,j)=\omega^{ij}$，逆变换 $\phi^{-1}(i,j)=\dfrac{\omega^{ij}}{k}$，其中 $\omega$ 是 $k$ 次单位根。
:::::success[证明]
只要证
$$
\begin{aligned}
\phi(i,x) \phi(j,x) &=\phi(i \oplus j, x)\\
\omega^{ix} \omega^{jx} &= \omega^{(i \oplus j)x}\\
\omega^{(i+j)x} &= \omega^{(i \oplus j)x}\\
(i+j)x &\equiv (i \oplus j) x \pmod k
\end{aligned}
$$
将条件加强为 $i+j \equiv i \oplus j \pmod k$。
写出 $i,j$ 的 $k$ 进制表示
$$
\begin{aligned}
i&=\sum_{n \ge 0} a_n k^n=a_0+a_1k+a_2k^2+\cdots\\
j&=\sum_{n \ge 0} b_n k^n=b_0+b_1k+b_2k^2+\cdots
\end{aligned}
$$
对普通加法 $i+j
\begin{aligned}
i+j&= \sum_{n \ge 0} (a_n+b_n) k^n=(a_0+b_0)+(a_1+b_1)k+\cdots\\
i+j &\equiv a_0+b_0 \pmod k
\end{aligned}
对不进位加法 i \oplus j
\begin{aligned}
i \oplus j &= \sum_{n \ge 0} ((a_n + b_n) \bmod k )k^n\\
i \oplus j &\equiv (a_0+b_0) \bmod k \pmod k\\
i \oplus j &\equiv a_0+b_0 \pmod k\\
\end{aligned}
二者均对 a_0+b_0 同余，证毕。
:::::
子集卷积
问题 10 给定 F,G ，求 H 满足 h_W=\sum \limits_{S \cup T=W \land S \cap T \ne \varnothing} f_Sg_T 。
这个问题被称作子集卷积 。子集卷积的组合意义是，将 W 不重不漏地划分为两个子集 (S,T) ，一个划分的权值为 f_S g_T ，并将权值求和。
$$
\begin{aligned}
[x^W y^{|W|}] H&=\sum_{S \cup T=W} [x^S y^{|S|}] F \times [x^{T} y^{|T|}] G\\
[y^{|W|}] H&=\sum _{|S|+|T| = |W|}[y^{|S|+|T|}] FG
\end{aligned}
$$
关于 $x$ 的乘法是并卷积，关于 $y$ 的乘法是多项式卷积。由于并卷积需要做 $n$ 次，复杂度 $O(n^2 2^n)$ 是瓶颈，$y$ 维度可以暴力卷积。
```cpp line-numbers
int n;
mint f[21][N], g[21][N], h[21][N];
void _main() {
cin >> n;
for (int s = 0; s < (1 << n); s++) cin >> f[popcount(s)][s];
for (int s = 0; s < (1 << n); s++) cin >> g[popcount(s)][s];
for (int i = 0; i <= n; i++) fwt_or(f[i], n, 1), fwt_or(g[i], n, 1);
for (int k = 0; k <= n; k++)
for (int i = 0; i <= k; i++)
for (int s = 0; s < (1 << n); s++) h[k][s] += f[i][s] * g[k - i][s];
for (int i = 0; i <= n; i++) fwt_or(h[i], n, -1);
for (int s = 0; s < (1 << n); s++) cout << h[popcount(s)][s] << ' ';
}
```
## 半在线卷积
**问题 11** 给定 $G,H,f_{\varnothing}$，求 $F$ 满足 $f_W=h_W\sum \limits_{S \cup T=W \land S \cap T \ne \varnothing} f_S g_T$。保证 $g_{\varnothing}=0,h_{\varnothing}=1$。
问题形如一个子集卷积，但卷积式包含 $f$，这种卷积被称作**半在线子集卷积**，简称半在线卷积。
考察 $S \cup T = W$ 且 $|S|+|T|=|W|$ 的条件。由 $g_{\varnothing}=0$ 可得 $|T| \ge 1$，进而 $|S|<|W|$。这表明，$f_W$ 的值只依赖 $|S|<|W|$ 的 $f_S$。我们以 $|W|$ 为枚举阶段，逐层计算 $F$ 即可。
具体地，我们逐层枚举 $k=1,2,\cdots,n$，在第 $k$ 层对 $y$ 卷积得到前缀贡献 $R=\sum \limits_{i=0}^{k-1} \text{FMT}([y^i]F) \cdot \text{FMT}([y^{k-i}]G)$，对 $R$ 做一个 FMT 逆变换后得到真实的 $R$，对 $|W|=k$ 的项乘上 $h_W$，再将 $R$ 做 FMT 传递给下一层。复杂度 $O(n^2 2^n)$。
```cpp line-numbers
int n;
mint f[21][N], g[21][N], h[N];
void _main() {
cin >> n >> f[0][0];
for (int i = 0; i < (1 << n); i++) cin >> g[popcount(i)][i];
for (int i = 0; i < (1 << n); i++) cin >> h[i];
for (int i = 1; i <= n; i++) fwt_or(g[i], n, 1);
fwt_or(f[0], n, 1);
for (int k = 1; k <= n; k++) {
static mint r[N];
fill(r, r + (1 << n), 0);
for (int i = 0; i < k; i++)
for (int s = 0; s < (1 << n); s++)
r[s] += f[i][s] * g[k - i][s];
fwt_or(r, n, -1);
for (int s = 0; s < (1 << n); s++)
if (popcount(s) == k) f[k][s] = r[s] * h[s];
fwt_or(f[k], n, 1);
}
for (int s = 0; s < (1 << n); s++) cout << f[popcount(s)][s] << ' ';
}
```
## 多项式复合
### 求逆
**问题 12** 给定 $G$，求 $F$ 使得 $F \times G=1$，$\times$ 为子集卷积。保证 $g_{\varnothing} \ne 0$。
对 $F \times G=1$ 代入子集卷积定义式
$$
\begin{aligned}
\sum_{T \subseteq S} f_T g_{S \setminus T}&=[S = \varnothing]
\end{aligned}
$$
若 $S \ne \varnothing$ 则
$$
\begin{aligned}
\sum_{T \subset S} f_T g_{S \setminus T}&=-f _S g_{\varnothing}\\
f_S&=-\dfrac{1}{g_{\varnothing}}\sum_{T \subset S} f_T g_{S \setminus T}
\end{aligned}
$$
这是一个 $h_S=-\dfrac{1}{g_{\varnothing}}$ 的半在线子集卷积，复杂度 $O(n^2 2^n)$。
```cpp line-numbers
int n;
mint f[21][N], g[21][N];
void _main() {
cin >> n;
for (int i = 0; i < (1 << n); i++) cin >> g[popcount(i)][i];
const mint h = mint(-1) / g[0][0];
for (int i = 1; i <= n; i++) fwt_or(g[i], n, 1);
f[0][0] = -h, fwt_or(f[0], n, 1);
for (int k = 1; k <= n; k++) {
static mint r[N];
fill(r, r + (1 << n), 0);
for (int i = 0; i < k; i++)
for (int s = 0; s < (1 << n); s++)
r[s] += f[i][s] * g[k - i][s];
fwt_or(r, n, -1);
for (int s = 0; s < (1 << n); s++)
if (popcount(s) == k) f[k][s] = r[s] * h;
fwt_or(f[k], n, 1);
}
for (int s = 0; s < (1 << n); s++) cout << f[popcount(s)][s] << ' ';
}
```
### $\exp
问题 13 给定 F ，求 \exp F=\sum \limits_{n \ge 0} \dfrac{F^n(x)}{n!} ，\times 为子集卷积。保证 f_{\varnothing}=0 。
考察 \exp F 的组合意义：将 S 不重不漏地划分为若干无标号子集，每种划分方式的权值为子集权值乘积，[x^S] \exp F 即为所有权值求和的结果。
上式具有这个组合意义的原因是，定义式相当于枚举划分的段数 n ，除以 n! 是消序。保证 f_{\varnothing}=0 表明我们不会划出空段，从而求和收敛，\exp F 有定义。
对着组合意义 DP：
可以做到 O(3^n) ，并不优秀。
进一步，考虑钦定 z=\max S ，此时 S \setminus \{z\}, T \in \{1,2,\cdots,z-1\} 。问题转化为半在线子集卷积，复杂度 O(n^2 2^n) 。
另一种引入形式元 y 的做法需要使用逆元，故泛用性不如组合意义做法。
int n;
u64 f[N], g[N], a[21][N], b[21][N];
void _main() {
cin >> n;
for (int i = 0; i < (1 << n); i++) cin >> f[i];
g[0] = 1;
for (int z = 0; z < n; z++) {
const int u = 1 << z;
for (int i = 0; i <= z; i++) fill(a[i], a[i] + u, 0), fill(b[i], b[i] + u, 0);
for (int s = 0; s < u; s++) a[popcount(s)][s] = f[s | u], b[popcount(s)][s] = g[s];
for (int i = 0; i <= z; i++) fwt_or(a[i], z, 1), fwt_or(b[i], z, 1);
for (int i = 0; i <= z; i++) {
static u64 r[N]; fill(r, r + u, 0);
for (int j = 0; j <= i; j++)
for (int s = 0; s < u; s++)
r[s] += a[j][s] * b[i - j][s];
fwt_or(r, z, -1);
for (int s = 0; s < u; s++)
if (popcount(s) == i) g[s | u] = r[s];
}
}
for (int i = 0; i < (1 << n); i++) cout << g[i] << ' ';
} \ln 问题 14 给定 F ，求 \ln F ，定义 \ln 为集合幂级数 \exp 的逆运算。保证 f_{\varnothing}=1 。
对 \exp 的转移进行变形
\begin{aligned}
f_S&=\sum_{T \subseteq S \setminus \{z\}} f_{S \setminus T \setminus \{z\}}[x^{T \cup \{z\}}] \ln F\\
f_S&=f_{\varnothing}[x^S] \ln F+\sum_{T \subset S \setminus \{z\}} f_{S \setminus T \setminus \{z\}}[x^{T \cup \{z\}}] \ln F\\
[x^S] \ln F&=f_S-\sum_{T \subset S \setminus \{z\}} f_{S \setminus T \setminus \{z\}}[x^{T \cup \{z\}}] \ln F
\end{aligned}
同理钦定 z =\max S 转化为半在线子集卷积，复杂度 O(n2^n) 。
int n;
u64 f[N], g[N], a[21][N], b[21][N];
void _main() {
cin >> n;
for (int i = 0; i < (1 << n); i++) cin >> f[i];
g[0] = 0;
for (int z = 0; z < n; z++) {
const int u = 1 << z;
for (int i = 0; i <= z; i++) fill(a[i], a[i] + u, 0), fill(b[i], b[i] + u, 0);
for (int s = 0; s < u; s++) b[popcount(s)][s] = f[s];
for (int i = 0; i <= z; i++) fwt_or(b[i], z, 1);
for (int i = 0; i <= z; i++) {
static u64 r[N]; fill(r, r + u, 0);
for (int j = 0; j <= i; j++)
for (int s = 0; s < u; s++)
r[s] += a[j][s] * b[i - j][s];
fwt_or(r, z, -1);
for (int s = 0; s < u; s++)
if (popcount(s) == i)
g[s | u] = f[s | u] - r[s], a[i][s] = g[s | u];
fwt_or(a[i], z, 1);
}
}
for (int i = 0; i < (1 << n); i++) cout << g[i] << ' ';
}练习
CF383E Vowels
给定 n 个集合 T_i ，T_i 是 \textcolor{red}{\tt{a \sim x}} 的子集。对字符集的所有子集 S 求出 \sum \limits_{i=1}^n [S \cap T_i \ne \varnothing] 。
:::::success[题解]
记 f_S=\sum \limits_{i=1}^n [S=T_i] ，题意即为求 G 满足
g_S=\sum_{S \cap T \ne \varnothing} f_T
对 S \cap T \ne \varnothing 做减法原理
\begin{aligned}
g_S&=\sum_{S \cap T \ne \varnothing} f_T\\
&=\sum_{S \subseteq U}f_S -\sum_{S \cap T=\varnothing}f_T\\
&=n-\sum_{T \subseteq (U \setminus S)} f_T
\end{aligned}
对 F 做一次 FMT 即可，复杂度 O(n+|\Sigma|2^{|\Sigma|}) 。
:::::
:::::info[代码]
const int N = 2e7 + 5;
i64 n, f[N];
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) {
string t; cin >> t;
int s = 0;
for (char c : t) s |= 1 << (c - 'a');
f[s]++;
}
fwt_or(f, 24, 1);
i64 res = 0;
const int u = (1 << 24) - 1;
for (int s = 0; s <= u; s++) {
i64 gs = n - f[u ^ s];
res ^= gs * gs;
} cout << res;
} :::::
ARC100E Or Plus Max
给定长为 2^n 的序列 a_0 \sim a_{2^n-1} 。对所有 k=1,2,\cdots,2^{n}-1 求 \max \limits_{i \ne j \land (i \text{ or } j) \le k}(a_i+a_j) 。
:::::success[题解]
考虑将条件变为 i \text{ or } j =k ，算出答案以后做一个前缀 \max 即可。
直接做是 (\max,+) 的 OR 卷积，但无法处理 i \ne j 的限制。
转而计算 a_i 的最大值和次大值，取二者之和作为答案，从而保证了 i \ne j 的限制。对 a_i 做一次 FMT 即可更新答案，不必再做逆变换。
复杂度 O(n2^n) 。
:::::
:::::info[代码]
const int N = (1 << 18) + 5;
using node = pair<int, int>;
int n, a[N];
node f[N];
node operator+ (const node& a, const node& b) {
vector<int> vec = {a.first, a.second, b.first, b.second};
sort(vec.begin(), vec.end(), greater<int>());
return {vec[0], vec[1]};
}
void _main() {
cin >> n;
for (int i = 0; i < (1 << n); i++) cin >> a[i], f[i] = {a[i], 0};
for (int i = 0; i < n; i++) {
for (int s = 0; s < (1 << n); s++) {
if (s >> i & 1) f[s] = f[s] + f[s ^ (1 << i)];
int res = 0;
for (int s = 1; s < (1 << n); s++) {
chkmax(res, f[s].first + f[s].second);
cout << res << '\n';
}
} :::::
ABC288G 3^N Minesweeper
给定长为 3^n 的序列 a_i 。
对于位置 i \in [0,3^n) ，位置 i 上有 b_i 个物品，且 b_i \in \{0,1\} 。给定 a_i=\sum \limits_{i \ominus j } b_j ，求 b_0 \sim b_{3^n-1} 。其中，\ominus 表示将 i,j 写成三进制后，逐位数码之差 \le 1 。
:::::success[题解]
容易得到 i \ominus j 的真值表，进而变换 b \to a 的位矩阵为
A=\begin{bmatrix}
1 & 1 & 0\\
1 & 1 & 1\\
0 & 1 & 1
\end{bmatrix}
对位矩阵求逆得到
A^{-1}=\begin{bmatrix}
0 & 1 & -1\\
1 & -1 & 1\\
-1 & 1 & 0
\end{bmatrix}
做一次 FWT 状物即可。复杂度 O(n3^n) 。
:::::
:::::info[代码]
const int N = 6e5 + 5;
int n, a[N];
void _main() {
cin >> n;
const int u = pow(3, n) - 1;
for (int i = 0; i <= u; i++) cin >> a[i];
for (int p = 1; p <= u; p *= 3)
for (int i = 0; i <= u; i += 3*p)
for (int j = 0; j < p; j++) {
int x = a[i + j], y = a[i + j + p], z = a[i + j + 2*p];
a[i + j] = y - z, a[i + j + p] = x + z - y, a[i + j + 2*p] = y - x;
}
for (int i = 0; i <= u; i++) cout << a[i] << ' ';
} :::::
CF662C Binary Table
给定一个 n \times m 的 01 矩阵 a_{i,j} ， 一次操作选择一行或一列，将其 flip。最小化 1 的数目并输出。
:::::success[题解]
记 T_j=\{i \mid a_{i,j}=1\} ，枚举 S 为进行操作的行号集合，答案为
\min_S \sum_{j=1}^m \min(|S \triangle T_j|, n-|S \triangle T_j|)
复杂度 O(m2^n) 无法通过。采用 01 转化 trick，设
\begin{aligned}
f_S&=[\exists j \in [1,m], T_j=S]\\
g_S&=\min(|S|,n-|S|)
\end{aligned}
代入答案式
\min_S \sum_{T} f_T g_{S \triangle T}
对 F,G 做对称差卷积后，取全局 \min 为答案。复杂度 O(nm+n2^n) 。
:::::
:::::info[代码]
const int N = 1.1e6 + 5, M = 1e5 + 5;
int n, m;
mint f[N], g[N];
char s[21][M];
void _main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
for (int j = 1; j <= m; j++) {
int v = 0;
for (int i = 1; i <= n; i++)
if (s[i][j] == '1') v |= 1 << (i - 1);
f[v]++;
}
for (int s = 0; s < (1 << n); s++) g[s] = min(popcount(s), n - popcount(s));
fwt_xor(f, n, 1), fwt_xor(g, n, 1);
for (int s = 0; s < (1 << n); s++) f[s] *= g[s];
fwt_xor(f, n, -1);
cout << *min_element(f, f + (1 << n));
}:::::
HDU5909 Tree Cutting
给定一棵 n 个点的树，第 i 个节点的点权为 a_i 。对每个 k=0,1,\cdots,m-1 求出，点权异或和为 k 的连通块数目。对 10^9+7 取模。
多测，T \le 10 ，n \le 10^3 ，m \le 2^{10} ，2 秒，128 MB。
:::::success[题解]
容易得到树形背包式 DP：
记 f_{u,S} 为满足以下条件的连通块 C 数目：
树形 DP 转移是逐子树加，对儿子 v 进行讨论：
不选择 v ，则 f'_{u,S} \gets f_{u,S} 。
选择 v ，枚举 T 的转移为 f'_{u,S \oplus T} \gets f_{u,S} f_{v,T} 。
DP 初值为 f_{u,a_u}=1 。
注意到 u 处的转移是对所有儿子做对称差卷积。设集合幂级数 F_u(x)=\sum\limits_{S} f_{u,S} x^S ，从而
F_u=x^{a_u}\prod_{v \in \text{son}(u)} (1+F_v)
乘法是对称差卷积。k 的答案即为 [x^k]\sum\limits_{u \in T} F_u 。
对所有 F 施加 \text{FWT} 变换，卷积化为对位乘法。由 \text{FWT} 的线性性，我们可以求出 \sum\limits_{u \in T} \text{FWT}(F_u) 再做逆变换，总复杂度 O(nm+m\log m) 。
一个细节是对初值 x^{a_u} 做 \text{FWT} 。根据 \phi(S,T)=(-1)^{|S \cap T|} 的构造，我们直接对每个位置赋值即可，复杂度 O(m) 。
:::::
:::::info[代码]
const int N = 1030, U = (1 << 10) - 1;
int n, m, a[N];
mint f[N][N], g[N];
vector<int> e[N];
void dfs(int u, int fa) {
for (int s = 0; s <= U; s++) f[u][s] = (popcount(s & a[u]) & 1) ? -1 : 1;
for (int v : e[u]) {
if (v == fa) continue;
dfs(v, u);
for (int s = 0; s <= U; s++) f[u][s] *= 1 + f[v][s];
}
for (int s = 0; s <= U; s++) g[s] += f[u][s];
}
void _main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
fill(g, g + U + 1, 0), dfs(1, -1), fwt_xor(g, 10, -1);
for (int i = 0; i < m; i++) cout << g[i] << " \n"[i == m-1];
} :::::
CF1119H Triple
给定 n 个集合幂级数 F_i=a\times x^{A_i}+v \times b^{B_i} + c\times x^{C_i} ，其中 a,b,c,A_i,B_i,C_i 给定，全集 U=\{0,1,\cdots,k\} 且 A_i,B_i,C_i \subseteq U 。
求 \prod\limits_{i=1}^n F_i ，乘法为对称差卷积，系数在 \mathbb{Z}_{998244353} 中运算。
:::::success[题解]
暴力卷积容易做到 O(nk 2^k) ，无法通过。
根据 [x^S]\text{FWT}(F_i)=\sum \limits_{T \subseteq U} (-1)^{|S \cap T|} [x^T] F_i ，由于 F_i 只有 3 个位置有值，于是
[x^S]\text{FWT}(F_i)=(-1)^{|S \cap A_i|} \times a+(-1)^{|S \cap B_i|} \times b+(-1)^{|S \cap C_i|} \times c
从而 O(2^k) 计算 \text{FWT}(F_i) ，复杂度 O(n2^k) 仍不可接受。
取 d_0=|S \cap A_i| \bmod 2, d_1=|S \cap B_i| \bmod 2, d_2=|S \cap C_i|\bmod 2 ，则 (d_0,d_1,d_2) 一共只有 8 种情况。设 \text{cnt}(d_0,d_1,d_2) 为 F_1 \sim F_n 中奇偶性与 (d_0,d_1,d_2) 对应的 F 的数目，则
[x^S] \text{FWT} \left(\prod_{i=1}^n F_i\right)=\prod_{d_0,d_1,d_2 \in \{0,1\}} \left( (-1)^{d_0} \times a+(-1)^{d_1} \times b+(-1)^{d_2} \times c\right)^{\text{cnt}(d_0,d_1,d_2)}
问题转化为，对所有 S 快速计算 \text{cnt}(d_0,d_1,d_2) 。
不妨单独考虑 A_i ，构造集合幂级数 G_1=\sum\limits_{i=1}^n x^{A_i} ，对 G_1 施加 \text{FWT} 变换
[x^S] \text{FWT}(G_1)=\sum_{i=1}^n (-1)^{|S \cap A_i|}=\sum_{d_0,d_1,d_2 \in \{0,1\}} (-1)^{d_0} \text{cnt}(d_0,d_1,d_2)
这启发我们将 A_i,B_i,C_i 各自作对称差，构造 8 个集合幂级数：
\begin{aligned}
G_0&=\sum_{i=1}^n x^{\varnothing} =n\\
G_1&=\sum_{i=1}^n x^{A_i}\\
G_2&=\sum_{i=1}^n x^{B_i}\\
G_3&=\sum_{i=1}^n x^{A_i\triangle B_i}\\
G_4&=\sum_{i=1}^n x^{C_i}\\
G_5&=\sum_{i=1}^n x^{A_i\triangle C_i}\\
G_6&=\sum_{i=1}^n x^{B_i\triangle C_i}\\
G_7&=\sum_{i=1}^n x^{A_i\triangle B_i\triangle C_i}\\
\end{aligned}
对固定的 S ，取出 \text{FWT}(G_0) \sim \text{FWT}(G_7) 的 x^S 次项系数，记作 g_0 \sim g_7 。
结论 g_0 \sim g_7 恰为 \text{cnt}(0,0,0) \sim \text{cnt}(1,1,1) 做一次规模为 2^3 的 \text{FWT} 所得的结果。
我们求出 G_0 \sim G_7 后做 8 个独立 \text{FWT} ，枚举 S \subseteq U 后求出 g_0 \sim g_7 ，并对 G 做一次 \text{FWT} 逆变换求得 \text{cnt}(0,0,0) \sim \text{cnt}(1,1,1) ，快速幂求出 S 对 [x^S] \text{FWT} \left(\prod\limits_{i=1}^n F_i\right) 的贡献，最终做 \text{FWT} 逆变换复原答案。
总复杂度 O(k2^k+2^k \log n) 。
:::::
:::::info[代码]
const int N = 1.5e5 + 5;
int n, k;
mint a, b, c, f[N], g[8][N], h[8];
void _main() {
cin >> n >> k >> a >> b >> c;
for (int i = 1, a, b, c; i <= n; i++) {
cin >> a >> b >> c;
g[0][0] += 1, g[1][a] += 1, g[2][b] += 1, g[3][a ^ b] += 1;
g[4][c] += 1, g[5][a ^ c] += 1, g[6][b ^ c] += 1, g[7][a ^ b ^ c] += 1;
}
for (int i = 0; i < 8; i++) fwt_xor(g[i], k, 1);
for (int s = 0; s < (1 << k); s++) {
for (int i = 0; i < 8; i++) h[i] = g[i][s];
fwt_xor(h, 3, -1); f[s] = 1;
for (int d = 0; d < 8; d++) {
mint q = 0;
(d & 1) ? q -= a : q += a;
(d >> 1 & 1) ? q -= b : q += b;
(d >> 2 & 1) ? q -= c : q += c;
f[s] *= q.pow(h[d].val);
}
}
fwt_xor(f, k, -1);
for (int i = 0; i < (1 << k); i++) cout << f[i] << ' ';
}:::::
P13275 [NOI2025] 集合
给定长为 2^n 的序列 a_0 \sim a_{2^n-1} 。记 f(S)=\underset{i \in S}{\text{and }} i ，特别地 f(\varnothing)=2^n-1 。求
\left(\sum_{P, Q} [P \cap Q=\varnothing][f(P)=f(Q)] \prod_{i \in (P \cup Q)} a_i\right) \bmod 998244353
其中 P,Q \subseteq \{0,1,\cdots,2^n-1\} 。
多测，T \le 3 ，n \le 20 ，2 秒，512 MB。
:::::success[题解]
钦定 S \subseteq f(P) \land T \subseteq f(Q) 。枚举 f(P)=f(Q)=W ，则 (S,T) 的容斥系数为 (-1)^{| S\triangle W|} (-1)^{|T \triangle W|}=(-1)^{|S|+|T|} 。
::::success[证明]
注意到
\begin{aligned}
|S \triangle W|&\equiv |S| + |W |\pmod 2\\
|T \triangle W|&\equiv |T| + |W |\pmod 2
\end{aligned}
从而
\begin{aligned}
|S \triangle W|+|T \triangle W| &\equiv|S|+|T|+2|W| \pmod 2\\
|S \triangle W|+|T \triangle W| &\equiv|S|+|T| \pmod 2\\
\end{aligned}
故有 (-1)^{|S \triangle W|+|T \triangle W|}=(-1)^{|S|+|T|} 成立，证毕。
::::
系数与 W 无关，而 W \subseteq (S \cap T) ，则 (S,T) 的容斥系数为 2^{|S \cap T|} (-1)^{|S|+|T|} 。
设 f(P) \subseteq S \land f(Q) \subseteq T 时的权值和为 q(S,T) 。讨论 i \in [0,2^n) 的选择：
若 S\nsubseteq i \land T \nsubseteq i ，不能放入 P 或 Q ，系数为 1 。
若 S\subseteq i \land T \nsubseteq i ，可以放入 P 或不放，系数为 a_i+1 。
若 S\nsubseteq i \land T \subseteq i ，可以放入 Q 或不放，系数为 a_i+1 。
若 S\subseteq i \land T \subseteq i ，可以放入 P ，放入 Q 或不放，系数为 2a_i+1 。
由乘法原理合并得到 q(S,T) 。这样
\begin{aligned}
q(S,T)&=\prod_{S\subseteq i \land T \nsubseteq i} (a_i+1) \prod_{S\nsubseteq i \land T \subseteq i} (a_i+1) \prod_{S\subseteq i \land T \subseteq i} (2a_i+1)\\
&=\prod_{S\subseteq i} (a_i+1) \prod_{T \subseteq i} (a_i+1) \prod_{(S \cup T) \subseteq i} \dfrac{2a_i+1}{(a_i+1)^2}
\end{aligned}
使用高维后缀积预处理
\begin{aligned}
f_S&=\prod_{S \subseteq i} (a_i+1)\\\
g_S&=\prod_{S \subseteq i} \dfrac{2a_i+1}{(a_i+1)^2}
\end{aligned}
从而 q(S,T)=f_S f_T g_{S \cup T} 。答案式
\begin{aligned}
\sum_{S,T} 2^{|S \cap T|} (-1)^{|S|+|T|} q(S,T)&= \sum_{S,T} 2^{|S \cap T|} (-1)^{|S|+|T|} f_S f_T g_{S \cup T}
\end{aligned}
利用二元容斥 |S \cap T|=|S|+|T|-|S \cup T| 将 2^{|S \cap T|} 拆开
\begin{aligned}
&\sum_{S,T\subseteq U} 2^{|S \cap T|} (-1)^{|S|+|T|} f_S f_T g_{S \cup T}\\
=&\sum_{S,T\subseteq U} 2^{|S|+|T|-|S \cup T|} (-1)^{|S|+|T|}f_S f_T g_{S \cup T}\\
=&\sum_{S,T\subseteq U} (-2)^{|S|} f_S \times (-2)^{|T|} f_T \times 2^{-|S \cup T|} g_{S \cup T}\\
=&\sum_{W\subseteq U} 2^{-|W|} g_{W} \sum_{S \cup T = W} (-2)^{|S|} f_S \times (-2)^{|T|} f_T
\end{aligned}
构造集合幂级数 F=\sum \limits_{S \subseteq U} (-2)^{|S|} f_S ，乘法为并卷积，从而
\sum_{W\subseteq U} 2^{-|W|} g_{W} \sum_{S \cup T = W} (-2)^{|S|} f_S \times (-2)^{|T|} f_T=\sum_{W\subseteq U} 2^{-|W|} g_{W}[x^W] F^2
注意处理 a_i \equiv -1 的情形：使用除零扩域的 trick，将每个数记作 a \times 0^b 的形式，乘除均有良定义。
总复杂度 O(n2^n) 。
:::::
:::::info[代码]
const int N = 1.1e6 + 5;
int n; mint a[N];
struct node {
mint a; int b;
node(mint _a = 0, int _b = 0) : a(_a), b(_b) {}
} f[N], g[N];
node operator* (const node& x, const node& y) {
return {x.a * y.a, x.b + y.b};
}
node& operator*= (node& x, const node& y) {return x = x * y;}
node operator/ (const node& x, const node& y) {
return {x.a / y.a, x.b - y.b};
}
node& operator+= (node& x, const node& y) {
if (x.b > y.b) x = y;
else if (x.b == y.b) x.a += y.a;
return x;
}
void _main() {
cin >> n;
for (int i = 0; i < (1 << n); i++) {
cin >> a[i];
if (a[i] == -1) f[i] = node(1, 1);
else f[i] = node(a[i] + 1, 0);
g[i] = (2*a[i]+1) / (f[i] * f[i]);
}
for (int i = 0; i < n; i++)
for (int s = 0; s < (1 << n); s++)
if (s >> i & 1) f[s ^ (1 << i)] *= f[s], g[s ^ (1 << i)] *= g[s];
for (int s = 0; s < (1 << n); s++) f[s] *= mint(-2).pow(popcount(s));
fwt_or(f, n, 1);
for (int s = 0; s < (1 << n); s++) f[s] *= f[s];
fwt_or(f, n, -1);
node res;
for (int s = 0; s < (1 << n); s++) res += f[s] * g[s] * ~mint(2).pow(popcount(s));
cout << res.a << '\n';
}:::::