容斥算法

容斥用交替符号修正“至少违反一个约束”中的重复计数；子集变换则把许多彼此重叠的子集和沿布尔格边逐维复用。两者的效率都取决于坏性质数量 $n$，以及固定交集或局部转移能否快速计算，而不是对象全集本身是否庞大。

满射计数例子 ​

设 $m,n$ 为非负整数。从 $m$ 个带标号元素映到 $n$ 个盒子的满射数，令 $A_i$ 为盒 $i$ 为空。固定 $S$ 为空盒后有 $(n-|S|{)}^m$ 个函数，因此满射数

本例每项只依赖 $|S|$，可以按空盒数量合并，进一步写成

因此只需 $n+1$ 个不同项，另计整数幂、二项式系数与大整数求和成本。这里约定 $0^0=1$，使空集到空集的唯一函数也被计入；$m=0<n$ 或 $n=0<m$ 时结果均为零。例如 $m=3,n=2$ 时得到 $2^3-2\cdot 1^3=6$。

数值与边界 ​

符号交替会产生巨大中间整数和严重浮点消去，精确计数应使用大整数或模运算；模数下减法需正规化。空集项符号和 $\bigcap _{\varnothing }{A}_i=\mathrm{\Omega }$ 约定不能漏。概率容斥的输入参数与算法的指数维度不同，不要把概率公式的项数当作多项式。

当每个子集的交集贡献可按子集状态复用时，容斥可与动态规划理路动态规划Dynamic programming在有限或良基的状态依赖上复用已计算结果的算法设计范式。结合，通过子集递推、zeta/Möbius 变换或按最后元素转移避免重复计算所有交。

原地 transform 不变量 ​

Zeta transform 处理完一组坐标后，数组 $F[S]$ 已对这些坐标上的所有子选择求和，而其余坐标保持与 $S$ 相同。处理下一位 $i$ 时，对含 $i$ 的 $S$ 执行 $F[S]\leftarrow F[S]+F[S\setminus \{i\}]$，恰加入缺少该位的子集。每轮只读取不含该位的源项，所以原地更新不会污染同轮来源。逆变换在同一位置做减法；不同坐标的更新算子彼此交换，因此逆变换可以沿原来的位次序执行。

Subset convolution 不是普通 zeta 后逐点相乘即可；通常还要按子集大小分层做 ranked transform，避免把重叠子集对计入。相邻 transform 的名字相近，运算域和目标卷积必须写清。

变换方向的最小核对例 ​

对两元素集合，zeta transform 把 $f[\varnothing ],f[\{1\}],f[\{2\}],f[\{1,2\}]$ 变成每个子集所有子集值之和。若原数组依次为 $(1,2,3,4)$，处理第一位后得到 $(1,3,3,7)$，再处理第二位得到 $(1,3,4,10)$。以同样位次序减去源项，先得 $(1,2,4,6)$，再恢复 $(1,2,3,4)$。

若在处理同一位时又反向更新源状态，会重复计数。数组项为大整数时，上述变换界只计算加减法次数，实际时间还取决于中间值位数。