本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/articles/15679108.html

容斥和组合数

自我介绍

吕欣。活跃在 2016 - 2019 年的一个 OIer。参加过 NOI 2015 (铁牌)，NOI 2016 (金牌）。2017 年进入清华大学姚班读书。在 2017 - 2019 年给各种 OI 比赛出过一些题（清华集训 2017 生成树计数；NOIWC 2019 I君的商店；NOI 2019 I君的探险；CTSC 2019 氪金手游），对（当时的）命题风格/环境/人有一定的了解。

邮箱：lyuxin1999@gmail.com

容斥好题

题1. （清华集训主旋律）给定一个 $N$ 个点的有向图，问这个图有多少个强连通子图。保证 $N\le 15$ 。

(也可以尝试去做完全图的情况： $N$ 个点的强连通图个数。)

解法

（图里可能有 $N^2$ 条边）

简单问题：给定一个有向图，问有多少个子图是 DAG。

DP: $f[S]$ 表示在点集 $S$ 之间删除一些边，使得剩下的图是个DAG的方案数。枚举哪些点的入度为 0，然后递归。

$f[S] = \sum_{T\subseteq S, T\neq \varnothing} 2^{\#edges(T,S-T)} \cdot f[S-T].$

但是这个递归式会算重：枚举的时候只保证了 $T$ 里的点入读为 0，但是 $S-T$ 可能也有入度为0的点。使用容斥：

$f[S] = \sum_{T\subseteq S,T\neq \varnothing} 2^{\#edges(T,S-T)} \cdot f[S-T]\cdot (-1)^{|T|-1}.$

使用这个DP计算，计算量是 $3^N$ 。

原题

一个图如果不强连通的话，那它就可以写成大于 1 个强连通分量连成的一个DAG。

强连通图的个数 = 所有图的个数 - 非强连通的个数。

尝试计算非强连通图的个数，枚举一个 $T$ ，让 $T$ 连成一个强连通图， $T$ 不接受来自 $S-T$ 的边。

$f[S] = ALL(S) - \sum_{T\subseteq S, T\neq \varnothing} f[T]\cdot 2^{ways(T,S-T)}\cdot ALL(S-T).$

ALL(S) 表示所有可能的图的个数。

令 $g[T]$ 表示：

把集合 $T$ 划分成若干块，每一块里连成一个强连通块。如果有奇数个块：产生 1 的贡献；如果有偶数个块：产生 -1 的贡献。
$g[T]$ 是所有的贡献之和。

$f[S] = ALL(S) - \sum_{T\subsetneq S, T\neq \varnothing} g[T]\cdot 2^{ways(T,S-T)}\cdot ALL(S-T).$

怎么算 $g$ ？给定一个集合 $S$ ，固定 $x\in S$ ，枚举 x 所在的强连通块:

$g[S] =f[S] -\sum_{T\subseteq S,x\in T} f[T]\cdot g[S-T]$

题2. （ZJOI 小星星）给定一个 $n$ 个点 $m$ 条边的无向图和一个 $n$ 个点的树。问把这个树“嵌入”到这个图里的方案数。保证 $n\le 17$ 。

做法 1：在树上DP，写 $f[x][S][y]$ 表示处理了 x 为根的子树，图里的S这些点已经被用了， $x$ 被映射到了图里 y 这个点上。

$f[x][S][y]\cdot f[ch[x]][S'][y'] \cdot \mathbf{1}[(y,y')\in G] \to f'[x][S\cup S'][y].$

直接做是 $O(3^n\cdot n^3)$ 。可以用 FMT（快速莫比乌斯变换） 优化到 $O(2^n\cdot n^{3})$ .

做法 2：容斥。如果不考虑“每个图里的点都要用”，写一个DP： $f[x][y]$ 表示 x 为根处理完，x 映射到 y 上的方案数。

这样做的话可能图里有些点没有被用到。枚举哪些点没有被用到，容斥。 $O(2^n\cdot n^3)$ 。

题3. （SHOI 黑暗前的幻想乡）给定一个 $n$ 个点的图。每条边被染上了 $n-1$ 种颜色里的一种。问有多少个生成树包含了 $n-1$ 个不同颜色的边。 $n\le 17$ 。（author：陈立杰）

如果没有颜色的限制：Matrix Tree 定理， $O(n^3)$ 。

有颜色限制：枚举哪些颜色没有被用到，做容斥。 $O(2^nn^3)$ 。

题4. (随机 K 大值)，现在有 $N$ 个独立的随机变量，第 $i$ 个变量 $X_i$ 服从 $[L_i, R_i]$ 上的均匀分布。问 $X_1,\dots, X_N$ 中的第 $K$ 大的数的期望。 $N\le 50, L_i,R_i\le 100$ 。

考虑简单版本： $L_i = 0, R_i = 100$ （从 [0, 100] 里均匀独立地随机 N 个数，问其中第 K 大的期望是多少。）

通常的容斥：有 $N$ 个限制条件，问有多少种方案 (1) 满足至少一个限制条件 / （2）不满足任何限制条件。

如果我们问 (3) 有多少种方案满足恰好 K 个限制条件？（3‘）有多少方案满足至少 K 个条件。

用 $f[S]$ 表示满足并且只满足集合 S 里的限制条件的方案数。用 $g[S]$ 表示至少满足了集合 S 里的限制条件的方案数。

$g[S] = \sum_{S\subseteq T} f[T].$

由反演公式：

$f[T] = \sum_{T\subseteq S} g[S]\cdot (-1)^{|S-T|}.$

那么问题 1 的答案是：

$\sum_{S\neq \varnothing} f[S] = ALL - f[\varnothing] = ALL - \sum_{S} g[S]\cdot (-1)^{|S|} = \sum_{S\ne \varnothing} g[S]\cdot (-1)^{|S|-1}.$

这里是因为 $g[\varnothing] = ALL$ 。

问题（3）：

$\sum_{|S| = K} f[S] = \sum_{|S|=K}\sum_{S\subseteq T} g[T]\cdot (-1)^{|T-S|} \\ = \sum_{|S|= K} g[T] \cdot \sum_{S\subseteq T,|S|= K} (-1)^{|T-S|} \\ = \sum_{|S|= K} g[T] \cdot {|S|\choose K}\cdot (-1)^{|S|-K} \\$

问题 (3’):

$\sum_{|S|\ge K} f[S] = \sum_{|S|\ge K}\sum_{S\subseteq T} g[T]\cdot (-1)^{|T-S|} \\ =\sum_{|T|\ge K} g[T]\sum_{|S|\ge K, S\subseteq T} (-1)^{T-S} \\ = \sum_{|T|\ge K} g[T] \cdot A(|T|, K).$

其中 $A(n, k) = \sum_{i = k}^{n} \binom{n}{i}\cdot (-1)^{n-i}$ .

（作为一个特殊情形，考虑 $k=1$ 的时候， $\sum_{i=1}^{n} (-1)^{n-i}{n\choose i} = (-1)^{n+1}$ ，此时得到奇偶错位求和）。

$ANS = \int_{0}^{R} \Pr[\text{第 K 大数} \ge x] dx \\ =\int_0^R \Pr[ \exists K 个数 \ge x ] dx\\ =\int_0^R (\sum_{|S|\ge K} f[S])dx \\ = \int_0^R (\sum_{|S|\ge K} g[S] \cdot c_{|S|})dx$

其中 $f[S]$ 表示 $X_i \ge x$ 对任意 $i\in S$ 成立，并且 $X_i < x$ 对任意的 $i\notin S$ 成立。

$g[S]$ 表示 $X_i\ge x$ 对任意 $i\in S$ 成立。 $c_{|S|}$ 是一个容斥系数。（这个概率就是 $\prod_{i\in S} \frac{R-x}{R}$ ，对 $x$ 积分即可）。

当 $L_i,R_i$ 不一定一样的时候：把 $[0, +\infty)$ 按照 $L_i, R_i$ 分段，每一段用上述技巧计算多项式，求积分。（ABC：Random K-th Max）

题5. (BZOJ 已经没有什么好害怕的了) 给定两个长度为 $N$ 的数组 $\{A_i\}$ 和 $\{B_i\}$ ，现在要把他们配对起来，使得恰好有 $K$ 对 $(A,B)$ 满足 $A\ge B$ ，求方案数。 $N\le 2000$ 。

考虑一个暴力容斥：

枚举集合 $A$ 里的 $t$ 个数构成的集合 $S$ ，要求他们必须匹配到比自己小的，其余的 $N-t$ 个数随意，求方案数。

暴力枚举完所有可能情况，可以算出 $g[t]$ ：表示在集合A里钦定了某 t 个数，保证它们的匹配对象比自己要小，其他随意的方案数。

用 $g[t]$ 反演出 $f[t]$ ：恰好有 t个A中的数，满足他们的匹配对象比自己小。答案就是 $f[K]$ .

优化：用一个DP来计算 $g$ 。令 $dp[i][j]$ 表示在集合 A 的前 i 个数里，钦定了 j 个数的匹配对象比自身小，的方案数之和。

$dp[i][j] \to dp[i + 1][j] \\ dp[i][j] \to \times ([比 A_{i+1} 小的数的个数] - j) \to dp[i + 1][j + 1].$

$dp[N][t]\cdot (N-t)! = g[t]$ 。

运算量是 $O(N^2)$

题6. (Atcoder Beginner Contest-???) 给定一个 $1\sim N$ 的排列 $P$ 。问有多少 $i\ne j$ 满足 $gcd(i,j) > 1$ 且 $gcd(P_i, P_j) > 1$ 。 $N\le 2\times 10^5$ 。

简单问题：有多少 $(i,j)$ 满足 $gcd(P_i, P_j) > 1$ （不考虑 $gcd(i,j) > 1$ 的限制）。容斥（莫比乌斯反演）

计算有多少 $(i, j)$ 满足 $2 | (P_i,P_j) $：加上。
计算多少满足 $3 | (P_i, P_j)$ ：加上。
计算有多少 $6|(P_i, P_j)$ ：减掉。
。。。
计算有多少 $d|(P_i, P_j)$ ：产生 $-\mu(d)$ 的贡献。

$ANS = \sum_{d=1}^N \mu(d) \cdot \binom{d的倍数的个数}{2}$

可以实现一个数据结构，支持插入一个数，删除一个数；询问集合里有多少个互质的pair。

每次插入/删除一个数 $x$ 的时候，枚举 $x$ 的约数 $d$ ，更新 $d$ 的倍数的个数。同时更新 ANS。
每次对数据结构的操作时间是 $2^{\omega(x)}\le \sqrt{N}$ ，其中 $\omega(x)$ 表示 x 不同的质因子的个数。

原题：现在带上了 i j 的限制。

只考虑 $2|(i, j)$ 的那些下标，计算一遍简单问题。产生 1 的贡献
枚举 $3 | (i, j)$ 的下标，计算一遍简单问题。产生 1 的贡献
。。。
枚举 $d|(i,j)$ 的下标，计算一遍简单问题。产生 $-\mu(d)$ 的贡献。

总共会对数据结构进行 $O(N\log N)$ 次更新。

计算量： $O(N\sqrt{N}\log N)$ .

组合数

定义： ${N\choose K}=\frac{N!}{K!(N-K)!}$ 为从 N 个物品中取出 K 个的方案数。

常用公式

$\sum_{i=0}^N \binom{N}{i} = 2^N$ .
$\sum_{i=0}^{N} \binom{N}{i}(-1)^i = 0$ .
$\sum_{i=0}^{N} \binom{N}{i}x^i = (1+x)^N$ .
$\sum_{i=0}^K \binom{N}{i}\binom{M}{K - i} = \binom{N+M}{K}$ . 范德蒙公式 $\sum_{i=0}^{N}{N\choose i}{M\choose i} = \sum_i {N\choose i}{M\choose M-i}={N+M\choose M}$
$\binom{N}{K}\binom{K}{i} = \binom{N}{i}\binom{N-i}{K-i}$ . 例子 $\sum_k f(i)\sum_i {N\choose K}{K\choose i} = \sum_i{N\choose i}f(i)\sum_K{N-i\choose K-i}=\sum_i f(i){N\choose i} 2^{N-i}$ .
$\binom{N}{i} = \binom{N - 1}{i - 1} + \binom{N-1}{i}=\binom{N - 1}{i - 1} + \binom{N-2}{i-1}+\binom{N-2}{i}=...=\sum_{t=i-1}^{N-1} {N-1\choose i-1}$ .
$\binom{N+1}{K+1} = \sum_{i=K}^{N} \binom{i}{K}$ (想象 N+1 个物品里选 K+1 个，我枚举第一个被选中的物品是第几个）。
- 等价地， $\binom{N+1}{K+1} = \sum_{i=K}^N \binom{i}{i-K}$ .
$\sum_{i=0}^{K} {N+1\choose i} =\sum_i {N\choose i}+{N\choose i-1}= 2\sum_{i=0}^{K}{N\choose i} - {N\choose K}$ .
Lucas 定理（SHOI 超能粒子炮；(例题2)[https://nanti.jisuanke.com/t/A1245])

题1. (LOJ 博弈论与概率统计）共有 $T$ 组询问，每次给定 $N,K$ ，计算 $\sum_{i=0}^{K}\binom{N}{i}$ ，保证 $K,N\le 10^5, T\le 10^5$ 。

令 $f(N,K)$ 表示答案。那么 $f(N,K)=f(N-1,K)\cdot 2 - {N\choose K}$ ， $f(N,K) = f(N, K-1)+{N\choose K}$ 。

当我们知道 $f(N,K)$ ，可以在 $O(1)$ 时间内算出 $f(N+1,K)$ 和 $f(N, K+1)$ 。

莫队， $O(T\cdot \sqrt{N+M})$ .

题2. (Atcoder BBQ Hard) 给定正整数数组 $(a_i)_{i=1}^N$ 和 $(b_j)_{j=1}^N$ ，计算 $\sum_{i\ne j} \binom{a_i+a_j+b_i+b_j}{a_i+a_j}$ ，保证 $N\le 10^5, a_i,b_j\le 2000$ 。

相当于从 $(-a_i, -b_i)$ 走到 $(a_j, b_j)$ ，每次向右或者向上一步的方案数。对 i、j 求和相当于需要自选起点 i 和终点 j。做一个DP。

题3. 有一个 $N\times N$ 的网格图，其中有 $K$ 个障碍点。计算从 $(1,1)$ 移动到 $(N,N)$ ，每次向右或者下走一步，中间不经过任何障碍点的方案数。保证 $N\le 10^5, K \le 2000$ 。

Skipped.

加强版：从 $(1, 1, 1)$ 移动到 $(N,M,K)$ ，每次选择一个维度走。

形如 $(i, i, i)$ 以及 $(N-i,M-i, K-i)$ 的点都是障碍点。求方案数。 $N,M,K\le 10^5$ 。

FFT + 生成函数 (多项式求逆)。

Skipped.

题4. (Atcoder - ARC118E) 有一个 $(N+2)\times (N+2)$ 的网格图。对于一个 $N$ 元排列 $P$ ，我们把 $\{(i,P_i)\}$ 标记为 $N$ 个障碍点，然后求从 $(0,0)$ 移动到 $(N+1,N+1)$ 的，不经过障碍的路径方案数。对于所有可能的排列 $P$ ，求不经过障碍的方案数的总和。 $N\le 100$ .

原题：排列的一部分已经填好，只需要填剩下的位置。

如果排列已经给定的话：容斥： $f[x][y]$ 表示走到 x、y 这个位置，经过并标记了偶数个障碍的方案数 - 经过并标记了奇数个障碍方案数。 $f[x][y]\to f[x+1][y]/f[x][y + 1]$ 。

排列没有给定的话：把生成排列的过程也放进DP 里. $f[x][y][k][flag]$ 表示在 x、y 这个位置，排列里确定了 k 个元素。flag：当前行 / 列是否已经放了一个障碍。经过并标记了偶数个障碍的方案数 - 经过并标记了奇数个障碍方案数。

枚举 (1) 在当前位置是否放障碍 /（2）向那个方向走。 $O(N^3)$ 。

进入一个新的行/列：可以知道当前行列是否已经有障碍。
因为有 flag，所以我们放的障碍一定保证不同行不同列。
我们记录了 k，我们放的障碍个数。这相当于说把排列里 K 个位置填好了。DP结束的时候乘 $(N-k)!$ 来保证生成的是一个排列。

题5. (AGE - Yes or No) 从一个 $N\times M$ 的网格图的 $(0,0)$ 移动到 $(N,M)$ ，经过一个点 $(i,j)$ 的时候可以获得 $\frac{\max(i,j)}{i+ j}$ 的得分。求所有可能的路径的得分之和。 $N, M\le 10^6$ 。

$\sum_{i,j} {i+j\choose i} \binom{N-i+M-j}{N-i}\frac{\max(i,j)}{i+j} \\ =\sum_i \frac{1}{i!(N-i)!} \sum_j \frac{(i+j)!\cdot (N+M-i-j)!}{j!(M-j)!} \frac{i}{i+j}\\ = \sum_i \frac{1}{i!(N-i)!}\sum_j$

正常做法：从小到大枚举 $i+j=s$ ，想计算

$\sum_{i} \binom{s}{i}\binom{N+M-s}{N-i} \frac{\max(i, j)}{s}$

我们分别计算

$A_i(s) =\frac{1}{s} \sum_i \binom{s}{i} \binom{N+M-s}{N-i}\cdot i \cdot [i\ge s/2] .$

和

$A_j(s) =\sum_i \binom{s}{i} \binom{N+M-s}{N-i}\frac{j}{i} \cdot [i < s/2]$

考虑从 $s$ 转移到 $s+1$ ：

$A_i(s+1)=\frac{1}{s+1}\sum_{i} \binom{s+1}{i}\binom{N+M-s-1}{N-i}\cdot i\cdot [i\ge (s+1)/2].$

$(s+1)A_i(s+1) - sA_i(s) \\ = \sum_{i} \left( \binom{s}{i} + \binom{s}{i-1} \right) \binom{N+M-s-1}{N-i}\cdot i\cdot [i\ge (s+1)/2] \\ -\sum_i \binom{s}{i}\left( \binom{N+M-s-1}{N-i} +\binom{N+M-s-1}{N-i-1}\right) \cdot i \cdot [i\ge s/2]$

这里注意到 $\binom{s}{i}\binom{N+M-s-1}{N-i}$ 可以和 $\binom{s}{i}\binom{N+M-s-1}{N-i}$ 消掉。 $\binom{s}{i-1}\binom{N+M-s-1}{N-i}$ 可以错位和 $\binom{s}{i}\binom{N+M-s-1}{N-i-1}$ 消掉。因为只需要特殊计算 $i\approx (s+1)/2$ 的 $O(1)$ 项即可。

(可以做 $O(1)$ 递推）。

神棍做法：不妨设 $N\ge M$ 。

$\frac{\max(i,j)}{i+j}$ 相当于说：还有 $i$ 个 “yes” 和 $j$ 个 “no” 在我的前面。我不知道他们出现的顺序，但是我想猜下一个位置是 yes 或者 no。我应该猜个数比较多的，我的成功率就是 $\frac{\max(i,j)}{i+j}$ .

原问题相当于说，从 $i,j = (n,m)$ 开始，每次猜下一个是 yes 或者 no，猜对了得分，猜错了不得分。问期望的总得分。

如果总是 $i\ge j$ 的话：我会一直猜 Yes，最后 $n+m$ 轮里有 $n$ 轮猜对，得 $n$ 分。

如果 $i=j$ ：

如果猜错了： $(i,j) => (i, j-1)$ 没有得分，但是仍然有 $i\ge j$ 。
如果猜对了： $(i,j)=>(i-1,j)$ ，这个局面和 $(i,j-1)$ 是等价的。所以这里相当于我"白赚"了0.5分。

所以答案是

$N + \frac{\sum_{i=0}^N{2i\choose i}{N+M-2i\choose N-i}}{2\cdot {N+M\choose N}}.$

题6. 组合数取模：计算 $\binom{N}{M}\bmod P$ 。

版本 1： $P= 10^9+7$ ， $N, M\le 10^9$ .

版本 2： $P$ 是一个小质数 (Lucas 定理).

版本 3： $P = 3^{10}$ ， $N,M\le 10^{18}$ .

版本 3 加强版： $P=3^{20}$ ， $N,M\le 10^{18}$ .

基于拉格朗日插值的多项式求和

拉格朗日插值. 假设 $P$ 是一个度数为 $D$ 的多项式。如果我们知道 $P$ 在 $D+1$ 个不同位置的取值 $(x_1,P(x_1)),\dots, (x_D,P(x_D))$ ，那么我们可以唯一地把 $P$ 写为

$P(x) = \sum_{i=1}^{D+1} P(x_i) \frac{\prod_{j\ne i} (x-x_j)}{\prod_{j\ne i}(x_i-x_j)}.$

多项式的部分和. 假设 $P:\mathbb{N}\to \mathbb{R}$ 可以表示为一个度数为 $D$ 的多项式，那么我们考虑函数 $Q:\mathbb{N}\to \mathbb{R}$

$Q(n) = \sum_{i\le n} P(i).$

可以证明 $Q$ 可以表示为一个度数为 $D+1$ 的多项式，并且这个表示方法是唯一的。

如果已知 $Q$ 在 $0,1,\dots, D$ 这些输入上的输出，那么对于任意给定的数 $n$ ，可以在 $O(D)$ 时间内计算出 $Q(n)$ 。算法：按照拉格朗日插值公式，只需要对每个 $i\in \{0,\dots, D\}$ 计算 $\prod_{j\ne i} (n - j)$ 和 $\prod_{j\ne i} (i - j)$ 。对于前者，我们只需要计算一个数列 $(n-0),(n-1),\dots, (n-D)$ ，然后取一个前缀积和一个后缀积即可。对于后者，可以发现它就是 $(i-1)!\cdot (D-i)!\cdot (-1)^{D-i}$ 。因此，整个计算可以在 $O(D)$ 时间内完成。