专栏文章

容斥

ll1ng21y12026
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2gugg
此快照首次捕获于
2025/12/01 19:29
3 个月前
此快照最后确认于
2025/12/01 19:29
3 个月前
查看原文

容斥

（零）简介

二项式反演

二项式反演经典形式：f(i)f(i) 恰 ii 个，g(i)g(i) 至少 ii 个：
g(x)=∑i=xn(ix)f(i)  ⟺  f(x)=∑i=xn(−1)i−x(ix)g(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)=∑T⊆Sg(T)  ⟺  g(S)=∑T⊆S(−1)∣S∣−∣T∣f(T)f(S)=\sum_{T\sube S} g(T)\iff g(S)=\sum_{T\sube S}(-1)^{|S|-|T|}f(T)
其中 S,TS,T 是两个集合，f(),g()f(),g() 是依题意构造的两个描述集合贡献的函数。

DAG 计数

常枚举至少有 kk 个 00 度点，容斥一下只需要求指定 kk 个 00 度点，剩下随便取的方案数。
例题：计数 nn 个带标号点的 DAG（有向无环图）。
设：f[i]f[i] 为 ii 个点的 DAG 方案数。DAG 至少存在一个 00 度点，枚举至少 jj 个 00 度点，它们都可以与剩下的点任意连边，且剩下的点只要求是一个 i−ji-j 大小的 DAG：
f[i]=∑j=1i(−1)j−1(ij)2j(i−j)f[i−j]f[i]=\sum_{j=1}^i (-1)^{j-1}\binom ij 2^{j(i-j)}f[i-j]

Min-Max 容斥

常用于期望问题中，将“最后一个操作的时间”转化为每个点“最先被操作的时间”。
E(max(S))=∑T⊆S,T≠∅(−1)∣T∣+1E(min(T))E(max(S))=\sum_{T\sube S,T\ne \empty} (-1)^{|T|+1}E(min(T))
证明：对于元素 xx 令其为 TT 中的最小值，令总共有 kk 个元素大于 xx，则 xx 的贡献为：
∑i=0k(−1)i+2(ki)x=(1−1)kx=[k=0]x\sum_{i=0}^{k} (-1)^{i+2}\binom{k}{i}x=(1-1)^kx=[k=0]x
故当 k=0k=0 即 xx 为最大值时，恰有 xx 的贡献。
感性理解是：对于 k>0k>0，除去当前最小值 xx 外随意在 kk 个较大元素中选择，选奇数、偶数个都有 2k−12^{k-1} 种方案，又带上系数 (−1)∣T∣+1(-1)^{|T|+1 } 故相互抵消。只有 k=0k=0 时不成立。
扩展：kth-max：
kthmax(S)=∑T⊆S,∣T∣≥k(−1)∣T∣−k(∣T∣−1k−1)min(T)kthmax(S)=\sum_{T\sube S,|T|\ge k} (-1)^{|T|-k}\binom{|T|-1}{k-1}min(T)

（一）应用与习题

P5339 [TJOI2019] 唱、跳、rap和篮球

比较典的容斥，需要计数技巧。
首先题目要求没有，自然想到钦定有 ii 对，然后容斥。
剩下的部分就是依次决定剩下的人的选择，如果直接枚举三维，即使加上前缀和优化也不行。
考虑这样：枚举 jj 表示有 jj 个人唱跳，剩下的人rap篮球，然后对于剩下的只需要再分一次。
再加上前缀和优化即可 O(n2)O(n^2)。

P4859 已经没有什么好害怕的了

二项式反演。但是推的时候没有注意到DP实际上求的是“剩下随意”的。
考虑一个DP：f[i][j]f[i][j] 表示 aa 选到第 ii 个，配对了 jj 个。但是注意转移时“不匹配”的实际上是“随意的”，即求出的是至少。所以 g(i)=f[n][i](n−i)!g(i)=f[n][i](n-i)!。
那么就可以用二项式反演来求“恰好”。
f(x)=∑i=xn(−1)i−x(ix)g(i)f(x)=\sum_{i=x}^n (-1)^{i-x} \binom{i}{x} g(i)

P3175 [HAOI2015] 按位或：min-max 容斥。

令位 ii 变为 11 的步数为 tit_i，题目等价于求 Emax(S)=max⁡i∈S(ti)Emax(S)=\max_{i\in S}(t_i)。即 SS 中最晚变为 11 的位的步数的期望。
min-max 容斥，可将其转化为第一次将 SS 中任意位变为 11 的期望步数。
E(max(S))=∑T⊆S,T≠∅(−1)∣T∣+1E(min(T))E(max(S))=\sum_{T\sube S,T\ne \empty} (-1)^{|T|+1}E(min(T))
证明：对于元素 xx 令其为 TT 中的最小值，令总共有 kk 个元素大于 xx，则 xx 的贡献为：
∑i=0k(−1)i+2(ki)x=(1−1)kx=[k=0]x\sum_{i=0}^{k} (-1)^{i+2}\binom{k}{i}x=(1-1)^kx=[k=0]x
故当 k=0k=0 即 xx 为最大值时，恰有 xx 的贡献。
感性理解是：对于 k>0k>0，除去当前最小值 xx 外随意在 kk 个较大元素中选择，选奇数、偶数个都有 2k−12^{k-1} 种方案，又带上系数 (−1)∣T∣+1(-1)^{|T|+1 } 故相互抵消。只有 k=0k=0 时不成立。
然后这题变成了对于一个集合 SS，有一些集合操作，如果这个操作操作到了 SS 中的一个元素，那么就计算 SS 第一次这样的时间。
由于操作之间相互排斥，故只需要知道 P(S)P(S) 表示这次操作操作到 SS 中元素的概率。期望时间即 1P(S)\frac{1}{P(S)}。
P(S)=∑S&T≠0a[T]P(S)=\sum_{S\&T\ne 0} a[T]
考虑换成 S&T=0S\&T=0 的 ∑a[T]\sum a[T]，发现这是 U⊕SU\oplus S 的子集和。高位前缀和即可。
注意判分母 =0=0 时无解。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...