我不会容斥
ty_mxzhn
·
·
算法·理论
upd：发现之前讲那个 AGC 题的时候讲错了（大体也差不多，推错了），而且集合划分容斥跑题了，故删去并增加更多题目。
前置知识
容斥 / 二项式反演
[n=0]=\sum_{i=0}^n\binom{n}{i}(-1)^i
二项式反演（常用形式）：
f_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(a_1,a_2,a_3,...,a_m) 为 a 中不同数的个数。
找到所有正整数序列 a 满足 a_1+a_2+a_3+...+a_m=n 的 f(a_1,a_2,a_3,...,a_m) 的和。对 998244353 取模。
## 题解
$$
\sum_{a}f(a)\\
=\sum_{p}\sum_{a}[p\in \{a\}]\\
$$
对于实际上序列 $a$ 中值为 $p$ 的集合 $S$，若 $S\neq \varnothing$ 就可以产生一点贡献。则根据 $\displaystyle [n=0]=\sum_{i=0}^n\binom{n}{i}(-1)^{i}$ 可以计算不合法方案。
容斥，枚举大小为 $i$ 的集合 $S$，并钦定集合中的数全部都是 $p$。记这种情况统计到的序列数量为 $f_i$ 则根据上式答案为 $\displaystyle \sum_{i=1}^n (-1)^if_i$。
$$
\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}
$$
最后面一项是 $m$ 次多项式，可以拉格朗日插值。
比较简单的一道题只是做一下铺垫。
# [P11817](https://www.luogu.com.cn/problem/P11817)
先刻画一下，一种方式是记序列 $a,b$ 表示每条边是由 $a_i \to b_i$。要求 $a_i\neq b_i$，但是还剩下无重边的条件不好刻画。
换个形态，设计长为 $2n$ 的序列 $a$ 进行 $i\to a_{2i-1},i\to a_{2i}$ 这样的连边方式，这太对了吧。于是把所有条件刻画出来。
+ 无重边：$a_{2i-1}\neq a_{2i}$。
+ 无自环：$i\neq a_{2i-1}$，$i\neq a_{2i}$。
+ $1\sim n$ 每个数出现两次。
使用类似上一题的写法：
$$
\sum_{a}\prod_{i=1}^n[a_{2i-1}\neq a_{2i}][i\neq a_{2i-1}][i\neq a_{2i}]\\
$$
为了方便单独拿出里面：
$$
[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]
$$
想一下这个式子啥意思，额这不是小学奥数韦恩图吗。反正乘法原理就是枚举每个 $i$ 选择这四种贡献的哪一个。接下来的部分和容斥没啥关系先不说。
参考：https://www.luogu.com.cn/article/ez7s5j0w
## 造计算机
$[x][y]$ 可以造出 $x\land y$。
$1-[x]$ 可以造出 $\neg x$。
所以感觉这个东西可以造出很多东西啊！有没有相关的题。
# [ARC096C](https://www.luogu.com.cn/problem/AT_arc096_c)
## 题目描述
求由若干个长度为 $n$ 的二进制数（$0\sim 2^n -1$）构成的不可重集合 $a$ 的数量，使得对于每一个二进制位，$a$ 中都至少有两个数在这一位上是 $1$。$1\le n\le 3000$。
## 题解
如法炮制：
$$
\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])
$$
看起来已经可以做了。还是乘法原理。如果选了 $[\mathrm{count}(a,i)=0]$ 就是直接丢掉这一位了，不管它。
假设有 $j$ 个数选了 $[\mathrm{count}(a,i)=1]$，这些 $1$ 可以分散到若干个数上，这是类似斯特林数的形式。但是还可以有至多一个 $0$。
然后，在式子里选了 $1$ 的也就是任选的位置可以让一个数分裂成若干个数：如果这是一个全 $0$ 则有 $2^{2^k}-1$ 种选法否则只是 $2^k$。预处理类似斯特林数的 dp 数组即可快速计算。
# 二维二项式反演 / 容斥
$$
\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。题意：有 $m$ 个小球，$n$ 种颜色，每次选出一个小球并记录颜色再放回袋子里。问你选出 $k$ 种颜色的期望操作次数。$1\le k\le n\le 10^3$，$n-k\le 10$，$1\le m\le 10^4$。
考虑拆贡献，拆分成第 $i$ 步只染了 $<k$ 种颜色的概率和。钦定 $j$ 种颜色一定没有染，则发现 $l$ 种未染颜色会产生 $\displaystyle \binom{l}{j}$ 次贡献，容斥系数和二项式定理一样！推完了。剩余题解去看题解区。
总结：Min-Max 容斥不如拆贡献。
# [QOJ9254](https://qoj.ac/problem/9254)
题意：随机一个长度为 $n$，值域为 $[1,m]$ 的正整数序列，求其中众数的出现次数的期望值。$1\le n\le 10^3,1\le m\le 10^9$。
套路的拆贡献，求 $\max cnt_i \ge k$ 的概率之和。$\max cnt_i\ge k$ 不好求改成 $\max cnt_i<k$。然后就相当于有系数：$\prod[cnt_i<k]$。
考虑 dp，一种暴力转移是值域从小往大选那 $n$ 个数，可以生成函数，但是可能没啥前途。考虑容斥。
设 $f_{i,j}$ 表示 $i$ 个数值域为 $[1,j]$，众数出现次数 $<k$ 的方案数。
转移首先是这个数任选，从 $jf_{i-1,j}$ 转移，然后钦定这个数为使得某个数出现次数刚好爆掉的时候，此时前 $i-1$ 个数恰好有 $k-1$ 个数与 $a_i$ 相同。从 $\displaystyle j\binom{i-1}{k-1}f_{i-k,j-1}$ 转移。
容易发现 $m-j\le \dfrac{n}{k}$，复杂度是 $O(\sum \dfrac{n^2}{k})=O(n^2\log n)$ 的。
总结：这个转移的时候容斥有点非常规的。
# [QOJ15326](https://qoj.ac/problem/15326)
手玩并注意到一个合法的线段树的合法权值方案为：
若一个点有两个叶子，则这两个叶子的权值不同，满足上述限制的前提下，有 $c$ 种这样的点，则方案为 $2^{c-1}$。
证明不难。考虑这种东西应该只能用钦定的方法算，钦定若干个权值不同的叶子被合并 $a$，若干个权值相同的叶子被合并 $b$。最后方案的 $a\subseteq a',b\subseteq b'$ 的贡献应该是 $[b'=0]2^{a'}$。容易发现容斥系数分别为 $1$ 和 $-1$。
由于“三角剖分等于线段树”可以发现：剩下乱选的方案是卡特兰数。计算合并成 $k$ 个物体的方案数即可。
这是经典问题，分治并 NTT，复杂度 2 log。
# [P10104](https://www.luogu.com.cn/problem/P10104)
考虑 $m=0$：假设 $a_{n+1}=C$，只需要最后和 $a_{n+1}=C-1$ 的方案相减即可得到答案，转化为异或和 $=0$。
数位 dp。枚举所有数与上界的 LCP 的最小值，后面会有一个数开始失控，第一次失控后面的达成条件方案数都可以直接算出，$O(n\log V)$。
考虑 $m>0$：容斥，选择一些边强制钦定相等，容斥系数 $-1$，划分成了若干个连通块，每个连通块内限制为 $a$ 的最小值的限制。
预处理联通块内的容斥系数和，这可以使用集合幂级数 $\ln$ 或者暴力 $O(3^n)$。我们也要暴力算出由连通块内最小值所构成的集合，每一个都做一遍“问题 $m=0$”。
记录 $f_{S,T}$ 表示当前连通块集合为 $S$，最小值集合为 $T$。复杂度 $4^n$。但是有说法是合并联通块的状态只有 $n2^n$ 种。$O(n3^n)$。
具体说法一下。首先先给 $a$ 排序。然后是按照最小值从小往大转移。我们需要记录当前选了哪些数和已经选了哪些最小值。
转移时，非最小值除外，剩下的位置最小值一定选了一个序列上的前缀，可以使用最大的最小值位置记录。则只需要记录非最小值的集合和最大的最小值位置，信息量 $O(n2^n)$。转移暴力合并。