子集卷积

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

名称中的“卷积”指把一个对象拆成两部分并汇总乘积，但分解坐标是子集的互补划分。它不同于按整数下标相加的普通数值卷积公理库卷积Convolution · 卷积运算在加法群上把两份测度按加法映射推前，汇总所有可合成为同一输出的输入贡献。，也不同于 XOR、OR、AND convolution；普通卷积只承担命名对照，不是快速子集算法的前置工具。

三元素的状态表 ​

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

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

代数与数值边界 ​

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

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

复杂度账本 ​

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

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

集合划分 DP ​

在子集动态规划公理库子集动态规划Subset dynamic programming以所有子集为状态执行精确指数动态规划，并准确计算转移枚举量。中，设 $cost(A)$ 是把非空子集 $A$ 作为一个块的权，$d{p}_j(S)$ 是把 $S$ 分成 $j$ 个有序块的总权，则

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