这里提供一道 CodeForces 上一道类似题目的题解

容斥

假设这里有一些元素，每个元素用 $ee$ 表示，每个元素可能在多个 $X_{i}X\_i$ 集合中，总共有 $nn$ 个集合 令 $XX$ 是所有 $X_{i}X\_i$ 的集合，

我们要求出元素的数量，也就是 $\mathrm{\mid }{\bigcup }_{i=1}^n{X}_i\mathrm{\mid }|\backslash bigcup\_\{i=1\}^\{n\}X\_i|$

其中，$\text{size}(Y)\backslash text\{size\}(Y)$ 代表 $YY$ 包含了几个 $XX$ 中的元素，也就是几个 $X_{i}X\_i$

CF559C - Gerald and Giant Chess

题意

给出一个 $H(H\le 10^5)H(H\backslash leq\; 10^5)$ 行 $W(W\le 10^5)W(W\backslash leq\; 10^5)$ 列的棋盘

棋盘上有 $n(n\le 2000)n(n\backslash leq\; 2000)$ 个格子是黑色的

在棋盘左上角有一个卒，每一步可以向右或者向下走一格，并且不能移动到黑色格子中

求：这个卒从左上角移动到右下角，一共有多少种可能的路线

思路（若 $n\le 20n\backslash leq\; 20$）

$ans=ans=$ 总方案数 $--$ 经过黑色格子的方案数 总方案数 $={\mathrm{\complement }}_{H+W}^H=\backslash complement\_\{H+W\}^\{H\}$

容斥

我们设 $ee$ 是一种从起点到终点，至少经过一个黑色格子的方案，经过黑色格子的方案数就是 $ee$ 的数量

$X_{i}X\_i$ 是从起点出发，一定经过 $ii$ 号黑点，到达终点的方案。显然如果某一种方案 $ee$ 经过了 $ii$ 号黑点，那么 $e\in X_{i}e\backslash in\; X\_i$

容斥的过程

我们状压枚举 $X_{i}X\_i$（就相当于枚举公式中的 $YY$）

如果枚举到的 $Y=\{X_p,X_q,X_r\}Y=\backslash lbrace\; X\_p,X\_q,X\_r\backslash rbrace$，对应的黑点编号就是 $p,q,rp,q,r$，交换它们的顺序，使得存在路径能顺利按顺序走完 $p\to q\to rp\backslash rightarrow\; q\backslash rightarrow\; r$，此时计算 $\{X_p,X_q,X_r\}\backslash lbrace\; X\_p,X\_q,X\_r\backslash rbrace$ 的交集，即： $\mathrm{\mid }{\bigcap }_{e\in Y}e\mathrm{\mid }=|\backslash bigcap\_\{e\backslash in\; Y\}e|=$起点$\to p\to q\to r\to \backslash rightarrow\; p\backslash rightarrow\; q\backslash rightarrow\; r\backslash rightarrow$终点 的方案数

思路（若 $n\le 2000n\backslash leq\; 2000$）

$ans={\sum }_{i=1}^{n}ans=\backslash sum\_\{i=1\}^\{n\}$ 起点到 $ii$ 号黑点的方案数（但不经过其它黑点） $\times \backslash times$ $ii$ 号黑点到终点的方案数

将所有黑点以行号为第一关键字，列号为第二关键字排序

令 $f_i=f\_i=$ 从起点到 $ii$ 号黑点，但不经过 $1\mathrm{～}i-11～i-1$ 号黑点的方案数

且黑点 $jj$ 可以到达黑点 $ii$

$ans=\sum f_i\cdot {\mathrm{\complement }}_{H-x_j+W-y_j}^{H-x_j}ans=\backslash sum\; f\_i\backslash cdot\; \backslash complement\_\{H-x\_j+W-y\_j\}^\{H-x\_j\}$