# 从卷积到反演

## 狄利克雷卷积

$$C[n]=\sum_{i=0}^{n}A[i]B[n-i]$$

$$C[n]=\sum_{ij=n}A[i]B[j]$$

$$(F*G)(n)=\sum_{ij=n}A(i)B(j)$$

$$[F*G](n)=\sum_{i+j=n}A(i)B(j)$$

## 多项式卷积及其反演

#### 存在单位元 ($e$)

$$e*f=f$$

$$e(n)=\begin{cases} 1 & (n=0)\\ 0 & (n\neq 0) \end{cases}$$

#### 一般反演

\begin{align} g_n &= \sum_{i=0}^{n}a_{n-i}f_i \\ f_n &= \sum_{i=0}^{n}b_{n-i}g_i \end{align}

\begin{aligned} g & =a*f \\ f & =b*g \end{aligned}

\begin{aligned} f & = b*g\\ f & = b*a*f\\ b*a & = e \end{aligned}

#### 二项式反演与矩阵

\begin{align} g_n &= \sum_{i=0}^{n}a_{ni}f_i \\ f_n &= \sum_{i=0}^{n}b_{ni}g_i \end{align}

\begin{align} \begin{bmatrix} g_0\\ g_1\\ g_2\\ \end{bmatrix} &= \begin{bmatrix} a_{00} & 0 & 0\\ a_{10} & a_{11} & 0\\ a_{20} & a_{21} & a_{22}\\ \end{bmatrix} \times \begin{bmatrix} f_0\\ f_1\\ f_2\\ \end{bmatrix}\\ \begin{bmatrix} f_0\\ f_1\\ f_2\\ \end{bmatrix} &= \begin{bmatrix} b_{00} & 0 & 0\\ b_{10} & b_{11} & 0\\ b_{20} & b_{21} & b_{22}\\ \end{bmatrix} \times \begin{bmatrix} g_0\\ g_1\\ g_2\\ \end{bmatrix}\\ \end{align}

\begin{align} \vec{F} &= A\times \vec{G}\\ \vec{G} &= B\times \vec{F}\\ \Rightarrow \vec{F} = A\times \vec{G} &= A\times B\times\vec{F} \\ A\times B &= E \end{align}

$$\sum_{j=m}^{n}b_{ni}a_{im} = \begin{cases} 0 & (n \neq m)\\ 1 & (n = m) \end{cases}$$

\begin{align} g_n & = \sum_{i=0}^{n}C_n^if_i \\ f_n & = \sum_{i=0}^{n}(-1)^{n-i}C_n^ig_i \end{align}

\begin{align} g_n & = \sum_{i=0}^{n}(-1)^iC_n^if_i \\ f_n & = \sum_{i=0}^{n}(-1)^iC_n^ig_i \end{align}

\begin{align} A\times B & = \sum_{i=m}^{n}b_{ni}a_{im}\\ & = \sum_{i=m}^{n}(-1)^{i-m}C_n^iC_i^m\\ & = \sum_{i=m}^{n}(-1)^{i-m}C_n^mC_{n-m}^{n-i}\\ & = (-1)^{i-m}C_n^m\sum_{i=m}^{n}C_{n-m}^{n-i}\\ & = (-1)^{n-i-m}C_n^m\sum_{i=0}^{n-m}C_{n-m}^{i}\\ & = (-1)^{n-m}C_n^m\sum_{i=0}^{n-m}(-1)^iC_{n-m}^{i}\\ & = (-1)^{n-m}C_n^m(1-1)^{n-m} \end{align}

## 狄利克雷卷积及其反演

#### 结合律 ($(f*g)*h=f*(g*h)$)

\begin{aligned} ((f*g)*h)(n) & =\sum_{ij=n}(f*g)(i)h(j) \\ & =\sum_{ij=n}(\sum_{kl=i}f(k)g(l))h(j) \\ & =\sum_{ijk=n}f(i)g(j)h(k) \end{aligned}

\begin{aligned} (f*(g*h))(n) & =\sum_{ij=n}f(i)(g*h)(j) \\ & =\sum_{ijk=n}f(i)g(j)h(k) \end{aligned}

#### 存在单位元 ($e$)

$$e(n) = \begin{cases} 1 & (n=1) \\ 0 & (n\neq 1) \end{cases}$$

#### 莫比乌斯函数

$$f(n)=\sum_{d|n}g(d) \Rightarrow g(d)=\sum_{d|n}f(d)\mu(\frac{n}{d})$$

$$f=u*g \Rightarrow g=f*\mu$$

\begin{aligned} f & = g*u \\ f*\mu & = g*u*\mu \\ f*\mu & = g*e \\ f*\mu & = g \end{aligned}

#### $\mu$的构造

$\mu(1)=1$

$\mu(n)=(-1)^k$，如果 n 可以写成 k 个不同质数的积

$\mu(n)=0$，其他 n

\begin{aligned} \sum_{d|n}\mu(d)& =\mu(1)+\mu(p_1)+\mu(p_2)+\dots+\mu(p_1p_2)+\dots+\mu(p_1p_2\dots p_k) \\ & =\sum_{i=0}^k C_k^i(-1)^i \\ & = 0 \end{aligned}

### 1 条评论

#### 【算法】 简单容斥模型 -boshi – K-XZY · 2018年10月12日 3:59 下午

[…] 本文将简单介绍几种常见的容斥模型，以及容斥方法。容斥和反演是离不开的，因为实际上它们就是同一种东西的两种表现形式，一种出现于小学课本，另一种出现于大学的教材。但是，容斥原理所运用的手段与技巧完全是基于反演理论的，因此，想熟练运用容斥原理，第一步就是完全搞清楚反演是什么。文章：从卷积到反演 […]