专栏文章

我不会容斥

tty_mxzhn
算法·理论参与者 7已保存评论 12

文章操作

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

当前评论
12 条
当前快照
1 份
快照标识符
@mlia78o0
此快照首次捕获于
2026/02/12 01:06
上周
此快照最后确认于
2026/02/19 01:15
12 小时前
查看原文
upd：发现之前讲那个 AGC 题的时候讲错了（大体也差不多，推错了），而且集合划分容斥跑题了，故删去并增加更多题目。

前置知识

容斥 / 二项式反演

[n=0]=∑i=0n(ni)(−1)i[n=0]=\sum_{i=0}^n\binom{n}{i}(-1)^i
二项式反演（常用形式）：
fi=∑j=i∞(ji)gjgi=∑j=i∞(ji)(−1)j−ifjf_i=\sum_{j=i}^{\infty} \binom{j}{i} g_j\\ g_i=\sum_{j=i}^{\infty} \binom{j}{i}(-1)^{j-i}f_j
其实容斥系数可以试的。另外显然这是在求一个矩阵的逆矩阵，可以暴力求出然后打表。
接下来总结一些我觉得比较好玩的容斥题！

QOJ8184

题目描述

设 f(a1,a2,a3,...,am)f(a_1,a_2,a_3,...,a_m) 为 aa 中不同数的个数。
找到所有正整数序列 aa 满足 a1+a2+a3+...+am=na_1+a_2+a_3+...+a_m=n 的 f(a1,a2,a3,...,am)f(a_1,a_2,a_3,...,a_m) 的和。对 998244353998244353 取模。
1≤n≤1018,1≤m≤500,m≤n1\le n\le 10^{18},1\le m\le 500,m\le n。

题解

∑af(a)=∑p∑a[p∈{a}]\sum_{a}f(a)\\ =\sum_{p}\sum_{a}[p\in \{a\}]\\
对于实际上序列 aa 中值为 pp 的集合 SS，若 S≠∅S\neq \varnothing 就可以产生一点贡献。则根据 [n=0]=∑i=0n(ni)(−1)i\displaystyle [n=0]=\sum_{i=0}^n\binom{n}{i}(-1)^{i} 可以计算不合法方案。
容斥，枚举大小为 ii 的集合 SS，并钦定集合中的数全部都是 pp。记这种情况统计到的序列数量为 fif_i 则根据上式答案为 ∑i=1n(−1)ifi\displaystyle \sum_{i=1}^n (-1)^if_i。
∑p=1n∑i=1m(−1)i(mi)(n−pi−1m−i−1)=∑i=1m(−1)i(mi)∑p=1n(n−pi−1m−i−1)\sum_{p=1}^n\sum_{i=1}^m(-1)^i\binom{m}{i}\binom{n-pi-1}{m-i-1}\\ =\sum_{i=1}^m(-1)^i\binom{m}{i}\sum_{p=1}^n\binom{n-pi-1}{m-i-1}
最后面一项是 mm 次多项式，可以拉格朗日插值。
比较简单的一道题只是做一下铺垫。

P11817

先刻画一下，一种方式是记序列 a,ba,b 表示每条边是由 ai→bia_i \to b_i。要求 ai≠bia_i\neq b_i，但是还剩下无重边的条件不好刻画。
换个形态，设计长为 2n2n 的序列 aa 进行 i→a2i−1,i→a2ii\to a_{2i-1},i\to a_{2i} 这样的连边方式，这太对了吧。于是把所有条件刻画出来。
  • 无重边：a2i−1≠a2ia_{2i-1}\neq a_{2i}。
  • 无自环：i≠a2i−1i\neq a_{2i-1}，i≠a2ii\neq a_{2i}。
  • 1∼n1\sim n 每个数出现两次。
使用类似上一题的写法：
∑a∏i=1n[a2i−1≠a2i][i≠a2i−1][i≠a2i]\sum_{a}\prod_{i=1}^n[a_{2i-1}\neq a_{2i}][i\neq a_{2i-1}][i\neq a_{2i}]\\
为了方便单独拿出里面：
[a2i−1≠a2i][i≠a2i−1][i≠a2i]=(1−[a2i−1=a2i])(1−[i=a2i−1])(1−[i=a2i])=1−[a2i−1=a2i]−[i=a2i−1]−[i=a2i]+2[a2i−1=a2i=i][a_{2i-1}\neq a_{2i}][i\neq a_{2i-1}][i\neq a_{2i}]\\ =(1-[a_{2i-1}=a_{2i}])(1-[i=a_{2i-1}])(1-[i=a_{2i}])\\ =1-[a_{2i-1}=a_{2i}]-[i=a_{2i-1}]-[i=a_{2i}]+2[a_{2i-1}=a_{2i}=i]
想一下这个式子啥意思，额这不是小学奥数韦恩图吗。反正乘法原理就是枚举每个 ii 选择这四种贡献的哪一个。接下来的部分和容斥没啥关系先不说。
参考：https://www.luogu.com.cn/article/ez7s5j0w

造计算机

[x][y][x][y] 可以造出 x∧yx\land y。
1−[x]1-[x] 可以造出 ¬x\neg x。
所以感觉这个东西可以造出很多东西啊！有没有相关的题。

ARC096C

题目描述

求由若干个长度为 nn 的二进制数（0∼2n−10\sim 2^n -1）构成的不可重集合 aa 的数量，使得对于每一个二进制位，aa 中都至少有两个数在这一位上是 11。1≤n≤30001\le n\le 3000。

题解

如法炮制：
∑a∏i=1n[count(a,i)≥2]=∑a∏i=1n(1−[count(a,i)=0]−[count(a,i)=1])\sum_{a}\prod_{i=1}^n[\mathrm{count}(a,i)\ge 2]\\ =\sum_{a}\prod_{i=1}^n(1-[\mathrm{count}(a,i)=0]-[\mathrm{count}(a,i)=1])
看起来已经可以做了。还是乘法原理。如果选了 [count(a,i)=0][\mathrm{count}(a,i)=0] 就是直接丢掉这一位了，不管它。
假设有 jj 个数选了 [count(a,i)=1][\mathrm{count}(a,i)=1]，这些 11 可以分散到若干个数上，这是类似斯特林数的形式。但是还可以有至多一个 00。
然后，在式子里选了 11 的也就是任选的位置可以让一个数分裂成若干个数：如果这是一个全 00 则有 22k−12^{2^k}-1 种选法否则只是 2k2^k。预处理类似斯特林数的 dp 数组即可快速计算。

二维二项式反演 / 容斥

∑S1≠∅∑S2≠∅sth.=∑S1≠∅∑T1⊆S1,≠∅∑S2≠∅∑T2⊆S2,≠∅(−1)∣T1+T2∣sth.=∑T1≠∅∑T2≠∅(−1)∣T1+T2∣STH.\sum_{S_1\neq \varnothing}\sum_{S_2\neq \varnothing}\mathrm{sth.}\\ =\sum_{S_1\neq \varnothing}\sum_{T_1\subseteq S_1,\neq \varnothing}\sum_{S_2\neq \varnothing}\sum_{T_2\subseteq S_2,\neq \varnothing}(-1)^{|T_1+T_2|}\mathrm{sth.}\\ =\sum_{T_1\neq \varnothing}\sum_{T_2\neq \varnothing}(-1)^{|T_1+T_2|}\mathrm{STH.}\\
CF2048G 题解：https://www.luogu.com.cn/article/2rrj6vur
这可能很简单，跳过。

Min-Max 容斥

我真的理解不了 Min-Max 容斥！其实不需要会！
例题：P4707。题意：有 mm 个小球，nn 种颜色，每次选出一个小球并记录颜色再放回袋子里。问你选出 kk 种颜色的期望操作次数。1≤k≤n≤1031\le k\le n\le 10^3，n−k≤10n-k\le 10，1≤m≤1041\le m\le 10^4。
考虑拆贡献，拆分成第 ii 步只染了 <k<k 种颜色的概率和。钦定 jj 种颜色一定没有染，则发现 ll 种未染颜色会产生 (lj)\displaystyle \binom{l}{j} 次贡献，容斥系数和二项式定理一样！推完了。剩余题解去看题解区。
总结：Min-Max 容斥不如拆贡献。

QOJ9254

题意：随机一个长度为 nn，值域为 [1,m][1,m] 的正整数序列，求其中众数的出现次数的期望值。1≤n≤103,1≤m≤1091\le n\le 10^3,1\le m\le 10^9。
套路的拆贡献，求 max⁡cnti≥k\max cnt_i \ge k 的概率之和。max⁡cnti≥k\max cnt_i\ge k 不好求改成 max⁡cnti<k\max cnt_i<k。然后就相当于有系数：∏[cnti<k]\prod[cnt_i<k]。
考虑 dp，一种暴力转移是值域从小往大选那 nn 个数，可以生成函数，但是可能没啥前途。考虑容斥。
设 fi,jf_{i,j} 表示 ii 个数值域为 [1,j][1,j]，众数出现次数 <k<k 的方案数。
转移首先是这个数任选，从 jfi−1,jjf_{i-1,j} 转移，然后钦定这个数为使得某个数出现次数刚好爆掉的时候，此时前 i−1i-1 个数恰好有 k−1k-1 个数与 aia_i 相同。从 j(i−1k−1)fi−k,j−1\displaystyle j\binom{i-1}{k-1}f_{i-k,j-1} 转移。
容易发现 m−j≤nkm-j\le \dfrac{n}{k}，复杂度是 O(∑n2k)=O(n2log⁡n)O(\sum \dfrac{n^2}{k})=O(n^2\log n) 的。
总结：这个转移的时候容斥有点非常规的。

QOJ15326

手玩并注意到一个合法的线段树的合法权值方案为：
若一个点有两个叶子，则这两个叶子的权值不同，满足上述限制的前提下，有 cc 种这样的点，则方案为 2c−12^{c-1}。
证明不难。考虑这种东西应该只能用钦定的方法算，钦定若干个权值不同的叶子被合并 aa，若干个权值相同的叶子被合并 bb。最后方案的 a⊆a′,b⊆b′a\subseteq a',b\subseteq b' 的贡献应该是 [b′=0]2a′[b'=0]2^{a'}。容易发现容斥系数分别为 11 和 −1-1。
由于“三角剖分等于线段树”可以发现：剩下乱选的方案是卡特兰数。计算合并成 kk 个物体的方案数即可。
这是经典问题，分治并 NTT，复杂度 2 log。

P10104

考虑 m=0m=0：假设 an+1=Ca_{n+1}=C，只需要最后和 an+1=C−1a_{n+1}=C-1 的方案相减即可得到答案，转化为异或和 =0=0。
数位 dp。枚举所有数与上界的 LCP 的最小值，后面会有一个数开始失控，第一次失控后面的达成条件方案数都可以直接算出，O(nlog⁡V)O(n\log V)。
考虑 m>0m>0：容斥，选择一些边强制钦定相等，容斥系数 −1-1，划分成了若干个连通块，每个连通块内限制为 aa 的最小值的限制。
预处理联通块内的容斥系数和，这可以使用集合幂级数 ln⁡\ln 或者暴力 O(3n)O(3^n)。我们也要暴力算出由连通块内最小值所构成的集合，每一个都做一遍“问题 m=0m=0”。
记录 fS,Tf_{S,T} 表示当前连通块集合为 SS，最小值集合为 TT。复杂度 4n4^n。但是有说法是合并联通块的状态只有 n2nn2^n 种。O(n3n)O(n3^n)。
具体说法一下。首先先给 aa 排序。然后是按照最小值从小往大转移。我们需要记录当前选了哪些数和已经选了哪些最小值。
转移时，非最小值除外，剩下的位置最小值一定选了一个序列上的前缀，可以使用最大的最小值位置记录。则只需要记录非最小值的集合和最大的最小值位置，信息量 O(n2n)O(n2^n)。转移暴力合并。

评论

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

正在加载评论...