各种反演

前言

oi中有各种反演，如二项式反演、莫比乌斯反演（欧拉反演）、单位根反演、斯特林反演。

形式一：设恰好 n 个满足条件的个数为 f(n)。设至多 n 个满足条件的个数为 g(n) 。

则 \displaystyle g(n)=\sum_{i=0}^{n}C_{n}^{i}f(i) 二项式反演得 \displaystyle f(n)=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}g(i)

形式二：设恰好 n 个满足条件的个数为 f(n)。设至少 n 个满足条件的个数为 g(n) ，一共有 k 个。

则 \displaystyle g(n)=\sum_{i=n}^{k}C_{i}^{n}f(i) 二项式反演得 \displaystyle f(n)=\sum_{i=n}^{k}(-1)^{i-n}C_{i}^{n}g(i)

形式一：若 \displaystyle g(n)=\sum_{d|n}f(d) 那么 \displaystyle f(n)=\sum_{d|n}\mu(\frac{n}{d})g(d)

形式二：若 \displaystyle g(n)=\sum_{n|d}f(d) 那么 \displaystyle f(n)=\sum_{n|d}\mu(\frac{d}{n})g(d)

特别地：\displaystyle[n=1]=\sum_{d|n}\mu(d)

有常用结论：当 n\le m 时有：

\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{m} [\gcd(i,j)=1]=\sum_{d=1}^{n}\mu(d)\Big\lfloor\frac{n}{d}\Big\rfloor\Big\lfloor\frac{m}{d}\Big\rfloor

莫比乌斯反演的一种特殊形式：\displaystyle n=\sum_{d|n}\varphi(d)

有常用结论：当 n\le m 时有：

\displaystyle \sum_{i=1}^{n} \sum_{j=1}^{m} \gcd(i,j)=\sum_{d=1}^{n}\varphi(d)\Big\lfloor\frac{n}{d}\Big\rfloor\Big\lfloor\frac{m}{d}\Big\rfloor

单位根反演常用于求某个多项式特定倍数的系数和。

形式：\displaystyle [n\mid k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ik}

形式：若 \displaystyle g(n)=\sum_{i=0}^{n}S(n,i)f(i) 则 \displaystyle f(n)=\sum_{i=0}^{n}(-1)^{n-i}s(n,i)g(i)

子集形式：若 \displaystyle g(S)=\sum_{T\sube S}f(T) ，则 \displaystyle f(S)=\sum_{T\sube S}(-1)^{|S|-|T|}g(T)

超集形式：若 \displaystyle g(S)=\sum_{S\sube T}f(T) ，则 \displaystyle f(S)=\sum_{S\sube T}(-1)^{|T|-|S|}g(T)

\displaystyle \max\{S\}=\sum_{T\sube S}(-1)^{|T|-1}\min\{T\}

\displaystyle \min\{S\}=\sum_{T\sube S}(-1)^{|T|-1}\max\{T\}