子集卷积

定义与直接枚举 ​

令底集 $N$ 有 $n$ 个元素，$f,g:2^N\to R$，其中 $R$ 先取交换环。子集卷积定义为

$$(f\ast g)(S)=\sum _{T\subseteq S}f(T)g(S\setminus T).$$

每一项把 $S$ 有序划分为 $T$ 与互补部分；两部分不重叠且并集恰为 $S$。它不同于 XOR/OR/AND convolution，也不同于按整数下标相加的普通数值卷积公理库卷积Convolution · 卷积运算在加法群上把两份测度按加法映射推前，汇总所有可合成为同一输出的输入贡献。。

单个 $S$ 需枚举 $2^{|S|}$ 个 $T$。为全部 $S\subseteq N$ 计算时，成对数量为

$$\sum _{S\subseteq N}{2}^{|S|}=3^n,$$

因为每个元素有“不在 $S$、在 $T$、在 $S\setminus T$”三种状态。位掩码循环减少常数，不改变 $3^n$。

三元素的状态表 ​

对 $S=\{a,b,c\}$，卷积包含八项：$T=\varnothing$ 与 $S$，三个单元素 $T$，以及三个双元素 $T$。例如 $T=\{a,c\}$ 的贡献是

$$f(\{a,c\})g(\{b\}).$$

若 $f(A)$ 是“把块 $A$ 作为第一部分的成本”，$g(B)$ 是剩余部分方案数，这八项恰枚举所有有序二分。无序划分还要处理两部分交换对称，不能直接除以 2，因为空块或相同类型可能形成固定点。

按秩 zeta 变换 ​

把函数按子集大小分层：

$$f_k(S)=\{\begin{array}{ll}f(S),& |S|=k,\\ 0,& \text{otherwise},\end{array}$$

并定义 ranked zeta transform

$${\hat{f}}_k(S)=\sum _{T\subseteq S}{f}_k(T).$$

对 $g$ 同样处理。接着在每个固定 $S$ 上按秩做长度 $n+1$ 的普通卷积：

$${\hat{h}}_k(S)=\sum _{j=0}^k{\hat{f}}_j(S){\hat{g}}_{k-j}(S).$$

这一步会暂时包含相交的 $f(A)g(B)$，因为只要求 $A,B\subseteq S$ 且 $|A|+|B|=k$。不能把 $\hat{h}$ 直接当答案；消除相交项是下一步 Möbius 逆变换的职责。

Möbius 反演与取对角 ​

对每个秩 $k$ 做子集格上的反演：

$$h_k(S)=\sum _{T\subseteq S}(-1{)}^{|S\setminus T|}{\hat{h}}_k(T).$$

最终答案取“秩与集合大小相等”的对角项

$$(f\ast g)(S)=h_{|S|}(S).$$

反演后仍满足 $|A|+|B|=|S|$ 且 $A\cup B=S$ 的项只能有 $A\cap B=\varnothing$，所以恰剩互补划分。这个基数论证是算法正确性的核心，而不是公式记忆。

复杂度账本 ​

所有 $k$ 的 zeta 与 Möbius 变换各做 $O(n^2{2}^n)$ 个环操作：有 $n+1$ 层函数，每层 fast zeta transform 为 $O(n{2}^n)$。每个 $S$ 上的秩卷积也需 $O(n^2)$，合计

$$O(n^2{2}^n)$$

时间。直接存所有 $(k,S)$ 值需 $O(n{2}^n)$ 环元素；滚动或覆盖数组能降低常数，但反演前不能丢掉仍被秩卷积使用的层。

若只求一个目标集合 $N$，直接 $2^n$ 枚举反而更便宜；快速算法的优势是同时得到全部 $S$，常用于子集 DP公理库子集动态规划Subset dynamic programming以所有子集为状态执行精确指数动态规划，并准确计算转移枚举量。的批量转移。

集合划分 DP ​

设 $cost(A)$ 是把非空子集 $A$ 作为一个块的成本，$d{p}_j(S)$ 是把 $S$ 分成 $j$ 个有序块的总权。则

$$d{p}_j(S)=\sum _{T\subseteq S}d{p}_{j-1}(T)cost(S\setminus T)$$

正是一层子集卷积。若目标是最小总成本，把求和与乘法换成 min 与加法会得到 min-sum 形式，但它不再处于有加法逆元的环中。

代数与数值边界 ​

快速 Möbius 反演需要减法，因此标准 $O(n^2{2}^n)$ 算法在环上成立；普通半环只有加法与乘法，不能无条件执行交替符号消去。min-plus 变体常需有界整数权重编码、距离积或额外多项式因子，不能把环算法的界原样搬过去。

浮点环在代数上可写减法，但大量交替求和会放大消去误差；模环实现则要确保模数符合应用的计数语义。输入数组下标通常按 $n$ 位 mask，$n>w$ 时每次子集操作不再是单字常数。

参考资料

• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Fourier Meets Möbius: Fast Subset Convolution, STOC, 2007.
• Petteri Kaski, Mikko Koivisto, Parameterized Algorithms and Inclusion–Exclusion, in Handbook of Exact Exponential Algorithms, 2011.
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015.