容斥

l1ng21y12026 · 2025-11-23 11:22:08 · 算法·理论

（零）简介

二项式反演经典形式：f(i) 恰 i 个，g(i) 至少 i 个：

g(x)=\sum_{i=x}^n \binom{i}{x} f(i) \iff f(x)=\sum_{i=x}^n (-1)^{i-x}\binom{i}{x} g(i)

更一般的形式为：

f(S)=\sum_{T\sube S} g(T)\iff g(S)=\sum_{T\sube S}(-1)^{|S|-|T|}f(T)

其中 S,T 是两个集合，f(),g() 是依题意构造的两个描述集合贡献的函数。

常枚举至少有 k 个 0 度点，容斥一下只需要求指定 k 个 0 度点，剩下随便取的方案数。

例题：计数 n 个带标号点的 DAG（有向无环图）。

设：f[i] 为 i 个点的 DAG 方案数。DAG 至少存在一个 0 度点，枚举至少 j 个 0 度点，它们都可以与剩下的点任意连边，且剩下的点只要求是一个 i-j 大小的 DAG：

f[i]=\sum_{j=1}^i (-1)^{j-1}\binom ij 2^{j(i-j)}f[i-j]

常用于期望问题中，将“最后一个操作的时间”转化为每个点“最先被操作的时间”。

E(max(S))=\sum_{T\sube S,T\ne \empty} (-1)^{|T|+1}E(min(T))

证明：对于元素 x 令其为 T 中的最小值，令总共有 k 个元素大于 x，则 x 的贡献为：

\sum_{i=0}^{k} (-1)^{i+2}\binom{k}{i}x=(1-1)^kx=[k=0]x

故当 k=0 即 x 为最大值时，恰有 x 的贡献。

感性理解是：对于 k>0，除去当前最小值 x 外随意在 k 个较大元素中选择，选奇数、偶数个都有 2^{k-1} 种方案，又带上系数 (-1)^{|T|+1 } 故相互抵消。只有 k=0 时不成立。

扩展：kth-max：

kthmax(S)=\sum_{T\sube S,|T|\ge k} (-1)^{|T|-k}\binom{|T|-1}{k-1}min(T)

比较典的容斥，需要计数技巧。

首先题目要求没有，自然想到钦定有 i 对，然后容斥。

剩下的部分就是依次决定剩下的人的选择，如果直接枚举三维，即使加上前缀和优化也不行。

考虑这样：枚举 j 表示有 j 个人唱跳，剩下的人rap篮球，然后对于剩下的只需要再分一次。

再加上前缀和优化即可 O(n^2)。

二项式反演。但是推的时候没有注意到DP实际上求的是“剩下随意”的。

考虑一个DP：f[i][j] 表示 a 选到第 i 个，配对了 j 个。但是注意转移时“不匹配”的实际上是“随意的”，即求出的是至少。所以 g(i)=f[n][i](n-i)!。

那么就可以用二项式反演来求“恰好”。

f(x)=\sum_{i=x}^n (-1)^{i-x} \binom{i}{x} g(i)

令位 i 变为 1 的步数为 t_i，题目等价于求 Emax(S)=\max_{i\in S}(t_i)。即 S 中最晚变为 1 的位的步数的期望。

min-max 容斥，可将其转化为第一次将 S 中任意位变为 1 的期望步数。

E(max(S))=\sum_{T\sube S,T\ne \empty} (-1)^{|T|+1}E(min(T))

证明：对于元素 x 令其为 T 中的最小值，令总共有 k 个元素大于 x，则 x 的贡献为：

\sum_{i=0}^{k} (-1)^{i+2}\binom{k}{i}x=(1-1)^kx=[k=0]x

故当 k=0 即 x 为最大值时，恰有 x 的贡献。

然后这题变成了对于一个集合 S，有一些集合操作，如果这个操作操作到了 S 中的一个元素，那么就计算 S 第一次这样的时间。

由于操作之间相互排斥，故只需要知道 P(S) 表示这次操作操作到 S 中元素的概率。期望时间即 \frac{1}{P(S)}。

P(S)=\sum_{S\&T\ne 0} a[T]

考虑换成 S\&T=0 的 \sum a[T]，发现这是 U\oplus S 的子集和。高位前缀和即可。

注意判分母 =0 时无解。