子集卷积 | Codeboy's Blog

形式陈述

定义与直接枚举

令底集 $N$ 为有 $n\ge0$ 个元素的有限集， $f,g:2^N\to R$ ，其中 $R$ 是环，不要求乘法交换或存在乘法单位元。子集卷积定义为

(f*g)(S)=\sum_{T\subseteq S}f(T)g(S\setminus T).

每一项把 $S$ 有序划分为 $T$ 与互补部分；两部分不重叠且并集恰为 $S$ 。

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

\sum_{S\subseteq N}2^{|S|}=3^n,

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

按秩 zeta 变换

把函数按子集大小分层：

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

并定义 ranked zeta transform

\widehat f_k(S)=\sum_{T\subseteq S}f_k(T).

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

\widehat h_k(S)=\sum_{j=0}^k \widehat f_j(S)\widehat g_{k-j}(S).

这一步会暂时包含相交的 $f(A)g(B)$ ，因为只要求 $A,B\subseteq S$ 且 $|A|+|B|=k$ 。下一步反演先保留并集恰为 $S$ 的项，再由秩与集合大小相等的条件排除相交；两步承担不同的筛选。

Möbius 反演与取对角

布尔格 $2^N$ 上的Möbius 反演使用系数 $(-1)^{|S\setminus T|}$ 。对每个秩 $k$ 做反演：

h_k(S)=\sum_{T\subseteq S} (-1)^{|S\setminus T|}\widehat h_k(T).

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

(f*g)(S)=h_{|S|}(S).

固定一对 $A,B$ ，它在反演后的系数是

\sum_{A\cup B\subseteq T\subseteq S}(-1)^{|S\setminus T|} =\begin{cases}1,&A\cup B=S,\\0,&A\cup B\ne S.\end{cases}

这是容斥消去：未覆盖 $S$ 的配对被消掉，覆盖 $S$ 的配对保留。随后取 $k=|S|$ ，再用 $|A|+|B|=|A\cup B|+|A\cap B|$ 推出交集为空。证明始终保留乘积 $f(A)g(B)$ 的因子次序，所以非交换环也适用。

例如 $N=\{a,b\}$ ，仅令 $f(\{a\})=g(\{a\})=1$ ，其余为零。反演后的 $h_2(\{a\})=1$ ，相交项并未消失；真正输出取 $h_1(\{a\})=0$ 。这清楚地区分了“精确覆盖”与“互不相交”。

直觉

子集卷积要把每个目标集合 $S$ 切成两块互不相交、并集恰为 $S$ 的有序划分。直接算法逐个猜第一块 $T$ ；快速算法先放宽条件，让 $A,B$ 只需同时落在 $S$ 内，再按大小记录 $|A|+|B|$ 。这一步故意混入了相交对，随后用 Möbius 反演消掉没有真正覆盖到当前集合的累计贡献，最后只取秩等于 $|S|$ 的对角线；“并集为 $S$ ”与“大小和为 $|S|$ ”合在一起，才迫使两块不相交。

名称中的“卷积”指把一个对象拆成两部分并汇总乘积，但分解坐标是子集的互补划分。它与按加法合成输入的群卷积采用不同的索引规则，也不同于 XOR、OR、AND convolution。秩层上的长度 $n+1$ 卷积是算法的辅助步骤；集合本身仍按不交划分组合。

在 S 为 a、b、c 且秩为三的例子中，未覆盖 c 的配对被反演消去，保留下来的对角项是不交划分 — 子集卷积的按秩变换与反演

例子与边界

三元素的状态表

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

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

若 $f(A),g(B)$ 是两类块的权，八项恰枚举所有有序二分的乘积权。要改成无序划分，需先让交换两块保持合法性及权重。对非空 $S$ ，互补两块不可能相等，交换没有固定点，即使一块为空也一样；每个无序对象恰对应两个有序对象。整数计数可据此除以二，一般环中则还须保证这项除法有定义。只有 $S=\varnothing$ 时， $(\varnothing,\varnothing)$ 才是固定点，须单独处理。

代数与数值边界

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

浮点运算只是对实数环运算的近似，本身不满足全部环公理，大量交替求和也可能放大消去误差。模环实现要确保模数符合应用的计数语义。输入数组通常以 $n$ 位 mask 为下标，若 $n$ 超过机器字长，一次集合操作不再是单字常数。只求一个目标集合 $N$ 时，直接枚举其 $2^n$ 个子集反而更便宜；快速算法的优势是同时得到全部 $S\subseteq N$ 的答案。

推论与应用

复杂度账本

对 $n\ge1$ ，所有 $k$ 的 zeta 与 Möbius 变换各做 $O(n^2 2^n)$ 个环操作：共有 $n+1$ 个秩层，每层 fast zeta 或 Möbius transform 需要 $O(n2^n)$ 。每个 $S$ 上的秩卷积也需 $O(n^2)$ ，计入初始化后，统一时间界为

O((n+1)^2 2^n).

直接存储全部 $(k,S)$ 值需要 $O((n+1)2^n)$ 个环元素；滚动或覆盖数组可以降低常数，但在相应秩卷积和反演完成前，不能丢掉仍会被引用的层。

集合划分 DP

在以含幺环取值的子集动态规划中，设 $cost(A)$ 是非空块 $A$ 的权，并令 $cost(\varnothing)=0$ 。定义 $dp_0(\varnothing)=1$ ，其余 $dp_0(S)=0$ ； $dp_j(S)$ 表示把 $S$ 分成 $j$ 个非空有序块的总乘积权。则

dp_j(S)=\sum_{T\subseteq S}dp_{j-1}(T)\,cost(S\setminus T)

正是一层子集卷积。连续应用可以批量计算不同块数的划分权。若目标是最小总成本，把求和与乘法换成 min 与加法会得到 min-sum 形式，但它不再处于有加法逆元的环中，不能直接声称同一个 Möbius 算法和复杂度。

参考资料

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Fourier Meets Möbius: Fast Subset Convolution, STOC, 2007，作者预印本，§2.2–2.4：按秩变换、反演与对角提取；§4.3：划分应用。
Marek Cygan et al., Parameterized Algorithms, Springer, 2015.

形式陈述 ​

定义与直接枚举 ​

按秩 zeta 变换 ​

Möbius 反演与取对角 ​

三元素的状态表 ​

代数与数值边界 ​

复杂度账本 ​

集合划分 DP ​

反向链接