https://sugarknri.hatenablog.com/entry/2022/11/19/231138

■いわゆる包除原理
$|\bigcup_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\bigcap_{i\in T}A_i|$
$|\bigcap_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\bigcup_{i\in T}A_i|$
N個の条件を全て満たすものの個数を求めてください→N個の条件いずれかに違反するものの個数を求めてください、と読み替えて包除しがち
2乗のDPになりがち

■min・max
$\max(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\min(T)$
$\min(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\max(T)$
期待値とかで使うらしい。ところでいわゆる包除原理とどういう関係にあるんですか？
追記：
S の元に適当に添字を付け、添字集合を $\Lambda_S$ とする。
$A_\lambda=\{x \mid x\leq S_\lambda\}$ と定め、ラムダに関して通常の包除原理を重み付き集合 $\mathbb{R}^\mathbb{Z}$ とみなして適用することで
$\{x\mid x\leq \max(S)\}\\ =\bigcup_{\lambda\in\Lambda_S}A_\lambda\\ =\sum_{\emptyset\neq \Lambda_T \subset \Lambda_S} (-1)^{|\Lambda_T|+1}\bigcap_{\lambda\in\Lambda_T}A_\lambda\\ =\sum_{\emptyset\neq \Lambda_T \subset \Lambda_S} (-1)^{|\Lambda_T|+1}\{x\mid x\leq \min(T)\}$
を得、これに対し通常の順序関係に関するメビウス変換を施すことで
$\{\max(S)\}=\sum_{\emptyset\neq \Lambda_T \subset \Lambda_S} (-1)^{|\Lambda_T|+1}\{\min(T)\}$
を得る。

出典

min-maxの式は
{x : x ≤ S₁ ∨ x ≤ S₂ ∨ .. ∨ x ≤ Sₙ}
= Σ[∅≠T⊆S] {x : x ≤ T₁ ⋀ x ≤ T₂ ⋀ .. ⋀ x ≤ Tₘ}(-1)^{#T-1}
でok?https://t.co/vEQQlqjAuS
— 37zigen (@37zigen) 2025年8月26日

■ゼータ変換・メビウス変換系（束上の累積和/imos・メビウスの反転公式）
累積和・imosは包除原理！（素振り）
・自然数の自然な大小関係に関する順序に対してやるやつ
・集合の包含関係に関する順序に対してやるやつ
・自然数の整除関係に関する順序に対してやるやつ
・分割の細分に関する順序に対してやるやつ

■逆行列を掛けるやつ
二項係数
$G(s) = \sum_{t=0}^s \binom{s}{t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} \binom{s}{t} G(t)$
スターリング数
$G(s) = \sum_{t=0}^s {s \brace t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brack t} G(t)$
$G(s) = \sum_{t=0}^s {s \brack t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brace t} G(t)$
係数がs-tのみで決まるなら畳み込み逆元だがそうではないので……？
追記：
これって集合の包含関係に関する順序についての反転、分割の細分に関する順序についての反転らしい。
集合の包含関係に関する順序についての反転は
$G(S)=\sum_{T\subset S}F(T) \Longleftrightarrow F(S)=\sum_{T\subset S}(-1)^{|S|-|T|}G(T)$
で、もしここで $|S|=|T| \Longrightarrow F(S)=F(T)$ が成り立つなら、シグマの部分を $\sum_{t=0}^{|S|}\sum_{T\subset S, |T|=t}$ と分解するとさっきの式が出てくる。知らなかったそんなの……

■主客転倒
これ包除じゃなくない？　でもメビウス関数とかでてきたら実質包除だろ（ガバ判定）
・N以下のsquare-free numberの数え上げを $\sum_{d\leq \sqrt{N}}\lfloor\frac{N}{d^2}\rfloor\mu(d)$ でやるやつ
[x=1]を $(\zeta*\mu)(x)=\sum_{d|x}\mu(d)$ と読み替えるのが本質。（畳み込みはDirichlet convolution）
包除じゃなくない？
・累積和の変形
$\sum_{x\leq N}F(x)=\sum_{x \leq N}(\mu*F)(x)\lfloor\frac{N}{x}\rfloor$
（畳み込みはDirichlet convolution）
これは本当に主客転倒してるだけ。包除なんも関係ない