【算法】卷积,反演,容斥(防抱死)

请注意,本文编写于 149 天前,最后修改于 149 天前,其中某些信息可能已经过时。

卷积

多项式卷积

$$ (F*G)[n]=\sum_{i=0}^{n}F[i]G[n-i] $$

狄利克雷卷积

$$ (F*G)[n]=\sum_{d|n}F[d]G[\frac{n}{d}] $$

卷积的性质

$$ \begin{gather} F*G=G*F &\mbox{交换律}\\ (F*G)*H=F*(G*H) &\mbox{结合律}\\ \epsilon*F=F &\mbox{单位元}\\ F*F^{-1} &\mbox{逆元} \end{gather} $$

一些函数

函数名称
$I(n)$恒等函数
$\mu(n)$莫比乌斯函数
$id(n)$单位函数
$\varphi(n)$欧拉函数
$\epsilon(n)$元函数

$$ I*\mu=\epsilon \\ I*\varphi=id\\ \mu*id=\varphi $$

熟练掌握这几个函数的意义,并且能够推导其中的关系

反演

定义

若有 $F=G*H$,其中 $F,H$ 已知,则可得 $G=absabsabs$

莫比乌斯反演

在狄利克雷卷积意义下

$$ F=G*I\\ \Downarrow\\ G=F*I^{-1} $$

根据前面的关系可以得到 $I^{-1}=\mu$ ,但是这是为什么呢?

$$ \mu[n]= \begin{cases} (-1)^{k} & (\prod_{i=1}^{k}p_i)\\ 0 & otherwise \end{cases} $$

$(I*\mu)[n]=\sum_{d|n}\mu[d]$
$=\mu[1]+\mu[p_1]+\mu[p_2]+\cdots+\mu[p_1p_2]+\cdots+\mu[p_1p_2\cdots p_k]$
$=\sum_{i=0}^{k}{k\choose i}(-1)^{i}$
$=(1-1)^{k}=[k=0]=[n=1]$
$=\epsilon$

作为卷积的逆运算,莫比乌斯反演有两种形式

形式一

$$ F[n]=\sum_{d|n}G[d]\\ \Downarrow\\ G[n]=\sum_{d|n}\mu[\frac{n}{d}]F[d] $$

形式二

$$ F[n]=\sum_{n|d,d\leq N}G[d]\\ \Downarrow\\ G[n]=\sum_{n|d,d\leq N}\mu[\frac{d}{n}]F[d] $$

一类矩阵反演

$$ A*B=I\\ G=A*F\\ F=B*G $$

二项式反演

形式一

$$ G[n]=\sum_{i=0}^{n}C_{n}^{i}F[i]\\ \Downarrow\\ F[n]=\sum_{i=0}^{n}(-1)^{n-i}C_{n}^{i}G[i] $$

形式二

$$ G[n]=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}F[i]\\ \Downarrow\\ F[n]=\sum_{i=0}^{n}(-1)^{i}C_{n}^{i}G[i] $$

斯特林反演

$$ G[n]=\sum_{i=1}^{n}s_{n}^{i}F[i]\\ \Downarrow\\ F[n]=\sum_{i=1}^{n}S_{n}^{i}G[i] $$

其中
$s_n^m:$ 将 $n$ 个元素划分为 $m$ 个集合的方案
$S_n^m:$ 将 $n$ 个元素划分为 $m$ 个圆排列的方案

子集反演

$$ G[S]=\sum_{T\subseteq S}F[T]\\ \Downarrow\\ F[S]=\sum_{T\subseteq S}(-1)^{|S-T|}G[T] $$

证明:

$$ \sum_{T\subseteq S}(-1)^{|T|}=\sum_{i=0}^{|S|}(-1)^{i}{|S|\choose i}=(1-1)^{|S|}=[|S|=0] $$

所以

$$ F[S]=\sum_{T\subseteq S}[|S-T|=0]F[T]\\ =\sum_{T\subseteq S}\sum_{P\subseteq S-T}(-1)^{|P|}F[T]\\ =\sum_{P\subseteq S}(-1)^{|P|}\sum_{T\subseteq S-P}F[T]\\ =\sum_{P\subseteq S}(-1)^{|P|}G[S-P]\\ =\sum_{T\subseteq S}(-1)^{|S-T|}G[T] $$

容斥

MIN-MAX容斥

$$ MAX(S)=\sum_{T\subseteq S}(-1)^{|T|+1}MIN(T)\\ MIN(S)=\sum_{T\subseteq S}(-1)^{|T|+1}MAX(T) $$

证明:

设 $MAX(S)=x$
对于不包含 $x$ 的每个集合,加入 $x$ 后,其数值不变,符号相反,贡献抵消
那么只有 $T={x}$ 时有贡献 $x$,得证

$MIN(S)$ 同理

由期望的线性性,该反演也能推广到期望范围

Comments

添加新评论