容斥算法

从恒等式到算法 ​

把容斥原理公理库容斥原理Inclusion–exclusion principle · PIE通过交集的交替和修正多个有限集合并集的重复计数。转成算法时，若全集对象集合为 $\mathrm{\Omega }$，坏性质对应 $A_1,\dots ,A_n$，满足所有约束的对象数为

$$|\mathrm{\Omega }\setminus \bigcup _i{A}_i|=\sum _{S\subseteq [n]}(-1{)}^{|S|}\left|\bigcap _{i\in S}{A}_i\right|.$$

算法价值取决于给定 $S$ 时交集计数是否足够便宜；$2^n$ 项不会因写成容斥就自动高效。

子集变换 ​

对函数 $f:2^{[n]}\to R$，zeta transform

$$F(S)=\sum _{T\subseteq S}f(T)$$

可用逐元素 DP：对每位 $i$，给含 $i$ 的状态加上去掉 $i$ 的值，总 $O(n{2}^n)$。Möbius inversion 把加法改为减法恢复 $f$。这像子集域上的 FFT 蝶形，但运算代数与普通卷积不同。

满射计数例子 ​

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

$$\sum _{S\subseteq [n]}(-1{)}^{|S|}(n-|S|{)}^m.$$

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

数值与边界 ​

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

原地 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 反向又更新源状态，会在一轮内重复计数。数值在交替求和中可能远超最终答案，模运算、整数位宽和浮点消去误差都要按应用另行处理。

参考资料

• Richard Karp, Dynamic Programming Meets the Principle of Inclusion and Exclusion, Operations Research Letters, 1982.
• Andreas Björklund et al., Fourier Meets Möbius: Fast Subset Convolution, STOC, 2007.