容斥算法

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

满射计数例子 ​

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

交集计数闭式便宜，容斥把“每盒非空”的全局约束转成 $2^n$ 指数算法。

数值与边界 ​

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

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

原地 transform 不变量 ​

Zeta transform 的第 $i$ 轮后，数组 $F[S]$ 已对 $S$ 在前 $i$ 个坐标上的所有子选择求和，而其余坐标保持与 $S$ 相同。对含 $i$ 的 $S$ 执行 $F[S]\leftarrow F[S]+F[S\setminus \{i\}]$ 恰加入缺少该位的子集。Möbius 逆按同序做减法。

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

变换方向的最小核对例 ​

对两元素集合，zeta transform 把 $f[\varnothing ],f[\{1\}],f[\{2\}],f[\{1,2\}]$ 变成每个子集所有子集值之和。按 bit 1、bit 2 依次执行 F[S]+=F[S\setminus\{i\}]，每条包含关系恰贡献一次；Möbius 逆变换把加号改为减号并按同样偏序恢复原数组。

原地实现时，外层必须固定一个元素 bit，内层只从不含该 bit 的旧侧流向含该 bit 的新侧。若对同一 bit 反向又更新源状态，会在一轮内重复计数。数值在交替求和中可能远超最终答案，模运算、整数位宽和浮点消去误差都要按应用另行处理。