何のページになるか良く分からないが，希望としては，包除原理を使う問題を集めたい?
記法:
- $x \in \mathbb{N}$ に対して $\bar{x} := \{0, 1, \ldots, x-1\}$ と書く．
- 全体集合が文脈から自明なとき，集合 $A$ の補集合を $A^{\text{C}}$ と書く．
- 集合 $A$ の冪集合を $\mathcal{P}(A)$ と書く．
定理の言明
$U$ を集合とする．各 $i \in \bar{n}$ に対して $A_i \subseteq U$ が定められている時， $$ \biggl|\bigcup_{i \in \overline{n}} A_i\biggr| = \sum \left\{ (-1)^{|X| + 1} \biggl|\bigcap_{i \in X} A_i\biggr| \;\middle|\; X \in \mathcal{P}(\bar{n}) \setminus \{ \varnothing \} \right\} $$
証明は，このブログの中だと ここ にある．
補集合を考えることによって，次が得られる． 偶奇による符号が反転していることに注意． $X$ が $\varnothing$ である場合も入っていて $\bigcap_{i\in \varnothing} {A_i}^{\text{C}} = U$ であることにも注意．
$$ \biggl|\bigcap_{i \in \overline{n}} A_i\biggr| = \sum \left\{ (-1)^{|X|} \biggl|\bigcap_{i \in X} {A_i}^{\text{C}} \biggr| \;\middle|\; X \in \mathcal{P}(\bar{n}) \right\} $$
使う問題
ABC456-G Count Holidays
次の部分問題を包除原理で解いている:
正整数 $n$ と $k$ が与えられる． 集合 $\bar{n}$ の部分集合 $X$ について，$p(X)$ を，$X$ に含まれる区間の長さの最大値とする． つまり，$i, i + 1, \dots, i + j - 1$ がすべて $X$ の要素になるような $i$ が存在するような $j$ の最大値である． $p(X) \leq k$ であるような $X \subseteq \bar{n}$ の個数を，mod 998244353 で求めよ． 時間計算量 $O(n/k)$．ただし，必要な階乗などは前計算してあって $O(1)$ で得られるとする．
解
TBW
ABC462-G Completely Wrong
長さ $N$ の整数列 $C$, $G$ で，$1 \leq C_i \leq N$，$1 \leq G_i \leq N$ であるものが与えられる． $1, 2, \dots, N$ の順列 $P$ で，すべての $i$ について $C_{P_i} \neq G_i$ となるものの個数を mod 998244353 で求めよ．$1 \leq N \leq 2\times 10^5$．
解
keywords: inclusion exclusion principle