学了个假容斥

Skeleton_Huo · 2025-11-21 18:56:48 · 算法·理论

引入

原本我对容斥原理的了解一直停在求若干集合的并集大小，但那只是容斥原理的一种应用，它既然叫原理，自然不只是一个公式。

容斥原理的基本思想是利用带有容斥系数的求和来修正原本会算重或算漏的统计。是一项用钦定算恰好的技术。

在最后一步，对于 m 链的方案数，我们试图用 f(m)=2^m \times m! 来计算。

我们考虑一下我们算重了什么，对于恰好 k 个二元环的解，我们统计了 2^k 次。我们希望通过容斥使得被统计恰好 1 次。

我们朴素地，一步一步考虑。恰好 1 个二元环的解被统计 2 次。我们钦定该二元环出现，其他部分用 f 计算，这样得到的结果包含了只有该二元环的解恰好一次。我们将答案减去该数，这样恰好一个二元环的答案就被正确统计了。

然后考虑恰好 2 个二元环的解，它在刚开始被统计 4 次，在第一步容斥中，每一个恰好 2 个二元环的解被统计了 2 \times 2 次（钦定第一个环 2 次，第二个环 2 次），于是现在的答案中被统计了 0 次。而钦定 2 个环的解包含恰好 2 个环的解恰好一次，然后补上。

再考虑恰好 3 个二元环，最初被算 2^3 次，在第一步减去 3 \times 2^{3-1} 次，第二步加上 3 \times 2^{3-2} 次。被算了 2 次，所以当前轮减去钦定 3 个二元环的方案中的一次。

到这里我们已经能看出答案（只考虑链）就是

\sum_{i=0}^r (-1)^i \times \binom{r}{i} \times f(m-i)

其中 r 为二元环的数量。

我们在这个过程中对于恰好 k 个二元环的统计次数的变化情况可以用

\sum_{i=0}^k (-1)^i \times \binom{k}{i} \times 2^{k-i}

来描述，由二项式定理，它恒等于 1。

事实上，容斥系数并不总是 (-1)^i。

例如上述例子中，如果不允许出现自环，则需要

\sum_{i=0}^k g(i) \times \binom{k}{i} \times 2^{k-i} = 0

我们需要令 g(i)=(-2)^i。答案也就变为

\sum_{i=0}^r (-2)^i \times \binom{r}{i} \times f(m-i)

这两个式子是在描述同一个过程，所以系数是同步修改的。

容斥问题都可以写成这种形式：f(k) 为钦定 k 个条件的答案，g(k) 为恰好 k 个条件的答案。

已知

f(k) = \sum_{i=k}^n c_{i,k} \times g(i)

求

g(k) = \sum_{i=k}^n d_{i,k} \times f(i)

这个方程是可解的，比如从 n 开始递推。

我们发现二项式反演也是容斥原理的一种应用。

例题写成该形式就是

f(k) = \sum_{i=k}^n g(i) \times \binom{i}{k} \times 2^{i-k}

两边乘 2^k，用 F(k)=2^k f(k) 和 G(k)=2^k g(k) 套用二项式反演公式，可以解得 g(k)。

从做题角度讲从朴素的容斥原理来考虑是最合理的。