关于狄利克雷卷积与莫比乌斯反演
Handezheng
·
·
算法·理论
狄利克雷卷积
定义常值函数I(n) = 1; \quad 线性函数id(n) = n;\quad 单位函数\epsilon(n) = [n=1]
狄利克雷卷积：h(n) = \sum_{d\mid n}f(d) g(\frac d n)
记作h = f * g，有如下性质：
- 交换律 f*g = g*f
- 结合律 (f*g)*h = f*(g*h)
- 分配率 f*(g+h) = f*g + f*h
-
f*h = g*h 的充要条件是f=g（h(1)\ne0）
-
若f*g=h，h是积性函数的充要条件是f,g均为积性函数
证明如下：
设两积性函数f(n),g(n)，且h = f*g;整数a,b互质
h(a) = \sum{d\mid a}f(d)\cdot g(\frac a d)\quad h(b) = \sum{d\mid b}f(d)\cdot g(\frac b d)
h(a)h(b) = \sum_{d_1\mid a}f(d_1)\cdot g(\frac a {d1})\times \sum{d_2\mid b}f(d_2)\cdot g(\frac{b}{d_2})
= \sum_{d\mid ab}f(d)\cdot g(\frac {ab} d) = h(ab)
狄利克雷逆元
关于狄利克雷卷积，其有逆运算，称之为狄利克雷逆元，如下：
若有 f*g=h和f=h*g^{-1}，则有 g*g^{-1}=\epsilon，即 g 的狄利克雷逆元，记作 g^{-1}。g^{-1} 的表达式如下：
因为有 (f*g)(n)=\epsilon(n)=\sum_{d\mid n}g(d)\cdot f(\frac n d)，
首先 f(1)\times g(1)=\epsilon(1)，得 g(1)=\frac{1}{f(1)}
对于 n>1，可发现等式右边总有一个 g(n)，将其提出，得到 g(n)f(1) + \sum_{d\mid n,d\ne n}g(d)f(\frac n d )=0 ，变形得到：
g(n) = -\frac{1}{f(1)}\sum_{d\mid n,d\ne n}g(d)f(\frac n d)
### 莫比乌斯函数
#### 定义
莫比乌斯函数 $\mu$ 是一个积性函数，而且它对应任意质数的取值都为 $−1$，任意质数的高次幂的取值都为 $0$。
基于此，对于 $\mu(n)$，对 $n$ 进行质因数分解，得到
$$
n = \prod_{k=1}^s p_k^{a_k}
$$
对于 $n=1$，有 $\mu(1)=1$，
否则：$若 \exists a_k >1,则 \mu(n)=0;\quad 否则若\forall a_k=1,那么\mu(n)=(-1)^s$。
#### 方程及性质
##### 方程
思考上文所述狄利克雷逆元相关知识，求 $I^{-1}$（设 $I^{-1}=f$）：
对于 $n=1$，有 $f(1)=1$；
否则，有
$$
f(n)=-\sum_{d\mid n,d\ne n}f(d)
$$
此时可以发现，对于任意质数 $p$，$f(p)=−f(1)=−1$，而 $f(p^2)=−[f(1)+f(p)]=0$。
容易发现，$p$ 的其他高次幂也都会等于 $0$，因为它们都等于 $−[f(1)+f(p)]$，因为其他 $f(p^n)$ 项都直接等于 $0$ 而被约去了。
这个函数其实就是莫比乌斯函数，我们可以得到它的表达式（$n>1$）:
$$
\mu(n) = -\sum_{d\mid n,d\ne n}\mu(d)
$$
##### 性质
由于 $I$ 是积性函数，且任意积性函数的狄利克雷逆元都是积性函数，所以莫比乌斯函数 $\mu$ 也是积性函数。
因此我们可以得到几点性质：
$$
\mu * I = \epsilon
$$
$$
\phi * I = id
$$
$$
id * \mu = id * I^{-1} = \phi
$$
关于莫比乌斯函数，它在狄利克雷生成函数中，等价于黎曼函数 $\zeta$ 的倒数
#### 利用欧拉筛求莫比乌斯函数
1. $\mu(1)=1$.
2. 当 $n$ 是质数时，$\mu(n)=-1$。
3. 当 $n$ 不是质数且因子 $i$ 中包含质数 $prime_j$ 时，说明 $n$ 有质数的高次幂作为因子，所以此时 $\mu(n)=0$。
4. 当 $n$ 不是质数且因子 $i$ 中不包含质数 $prime_j$ 时，说明 $i$ 与 $prime_j$ 互质；又因为莫比乌斯函数是积性函数，且第2条可以得到 $\mu(prime_j)=-1$，所以此时 $\mu(n)=-\mu(i)$。
由此 $O(n)$ 可以得到莫比乌斯函数的任意值。
### 莫比乌斯反演
反演结论
$$
\sum_{d\mid \gcd(i,j)}\mu(d) = [\gcd(i,j)=1]
$$
## 题
1. [P2522](https://www.luogu.com.cn/problem/P2522) 莫比乌斯反演+整除分块[解法](https://www.luogu.com.cn/paste/4k7yy6l3) AC[代码](https://www.luogu.com.cn/record/200280358)
2. [SP5971](https://www.luogu.com.cn/problem/SP5971) 莫比乌斯反演+莫比乌斯函数关于狄利克雷卷积的性[解法](https://www.luogu.com.cn/paste/2z19su96) AC[代码](https://www.luogu.com.cn/record/200635032)
## 范德蒙德卷积
$$
\sum_{i=0}^{k} {n \choose i} {m \choose k-i}={n+m \choose k}
$$