狄利克雷相关
command_block
2020-02-01 17:14:10
# 狄利克雷前缀和
首先需要掌握 [位运算卷积(FWT)与其扩展](https://www.luogu.com.cn/blog/command-block/wei-yun-suan-juan-ji-yu-ji-kuo-zhan) ,否则可能无法理解某些内容。
设 $A^+=A*I$ ,即倍数求和, $A^-=A*\mu$ ,则倍数差分(逆运算)。
倍数求和直接枚举倍数暴力算即可,复杂度$O(n\log n)$.
倍数差分可以莫比乌斯反演:
设容斥系数为$g$,有$A^-[n]=\sum\limits_{i=1}g(i)A[i]=\sum\limits_{i=1}g(i)\sum\limits_{i|j}A^-[j]$
提取$A^-[j]$的贡献系数 : $\sum\limits_{i|j}g(i)=[j=n]$,即能推出$g(i)=[n|i]\mu(i/n)$
回代可得$A^-[n]=\sum\limits_{n|i}\mu(i/n)A[i]$,这同样可以枚举倍数达到$O(n\log n)$.
我们在计算 `and` 卷积的时候,可以暴力枚举补集,但是复杂度为$O(3^n)$不优。
类似地,我们在这里暴力枚举倍数也不够优。
- [P5495 Dirichlet 前缀和](https://www.luogu.com.cn/problem/P5495)
这是前缀和而不是本文的倍数求和,不过原理类似。
考虑每个质因数是一维,做高维前缀和(其实就是卷 $I$ ),代码是这样的:
```cpp
for(int i=1;i<=tn;i++)
for(int j=1;j*p[i]<=n;j++)
F[j*p[i]]+=F[j];
```
类似地,有约数前缀差分(其实就是卷 $\mu$ )
```cpp
for(int i=1;i<=tn;i++)
for(int j=n/p[i];j;j--)
F[j*p[i]]-=F[j];
```
以后想卷 $I,\mu$ 的时候,这样写会比暴力狄利克雷卷积快得多,还不用筛。
约数后缀和:
```cpp
for(int i=1;i<=tn;i++)
for(int j=n/p[i];j;j--)
F[j]+=F[j*p[i]];
```
约数后缀差分:
```cpp
for(int i=1;i<=tn;i++)
for(int j=1;j*p[i]<=n;j++)
F[j]-=F[j*p[i]];
```
根据埃氏筛法的复杂度分析,上述代码的复杂度均为 $O(\sum_{p}^n\frac{n}{p})=O(n\log\log n)$
- 例题 : [P2714 四元组统计](https://www.luogu.com.cn/blog/command-block/solution-p2714)
- 求 $\gcd$ 卷积
形如 $C[n]=\sum\limits_{(i,j)=n}A[i]B[j]$ 的卷积,被称为 $\gcd$ 卷积。
我们可以先计算 $C^+[n]=\sum\limits_{n|(i,j)}A[i]B[j]$ ,然后再差分即可得到 $C$ .
$C^+[n]=\sum\limits_{n|(i,j)}A[i]B[j]$
$=\sum\limits_{n|i,n|j}A[i]B[j]$
$=\big(\sum\limits_{n|i}A[i]\big)\big(\sum\limits_{n|j}B[j]\big)$
$=A^+[i]B^+[j]$
- 这从向量变换的角度容易理解:
$\gcd$ 的本质就是对每个质因子维度取 $\min$.
类比 `and` 卷积,先要做高维后缀和,点乘再差分即可得到答案。
对应到 $\gcd$ 卷积上,即先要倍数求和,点乘再倍数差分。
- 快速狄利克雷卷积
可用于加速某些题目的预处理。
我们按照枚举倍数的传统方法计算狄利克雷卷积,复杂度是 $O(n\log n)$ 的。
前面讲到过,对于卷 $I,\mu$ 的特殊情况,可以理解成在高维空间的前缀和/差分,从而使用高维变换优化。
实际上,对于任意的积性函数,也有类似的方法。
设 $F$ 为积性函数, $G$ 不是,欲求 $F*G$ 的前 $n$ 项。
我们把 $F$ 分解为若干个只和某个素数 $p$ 有关的函数(变换) 的卷积,即 :
$F_p(n)=\begin{cases}F(n)&(n=p^k)\\0&{\rm otherwise}\end{cases}$
然后则有 $F=\prod\limits_{p\in {\rm Prime}}F_p(n)$ ,这里的乘法是狄利克雷卷积。
简略证明 : 容易发现 $F_{p_1}*F_{p_2}$ 能够得到 $n=p_1^{k_1}p_2^{k_2}$ 处的所有值,可以进一步推广到不交的质数集合卷积的情况。
也即 : 可以把一个积性函数拆成 $\pi(n)$ 个只与单个质数有关的积性函数卷积。
我们把这些函数分别卷到 $G$ 上去,就能得到答案。
考虑 $(G*F_p)(n)=\sum\limits_{d|n}G(n/d)F_p(d)$
$=\sum\limits_{p^k|n}G(n/p^k)F_p(p^k)$
考虑枚举每个 $p^k$ 的倍数计算该和式。(可以预先保存需要的 $G$)
考虑单个质数 $p$ ,其贡献的复杂度为 $O\Big(\sum\limits_{k=1}^{∞}n/p^k\Big)$
使用等比数列可算得其为 $O(\frac{n}{p-1})$ 其实也与 $O(\frac{n}{p})$ 同级。
所以复杂度仍然是 $O(\sum_{p}^n\frac{n}{p})=O(n\log\log n)$。
此外,对于每个 $p^k$ 都需要求出 $F$ ,这样的 $p^k$ 的个数是 $O(n/\log n)$ 的。
对于 $p\leq \sqrt{n}$ 的部分,贡献不超过 $O(\pi(\sqrt{n}\log n))=O(\sqrt{n})$ ,可不计。
对于 $p>\sqrt{n}$ 的部分,指数只能是 $1$ 贡献不超过 $O(\pi(n))=O(n/\log n)$。
所以,我们只需要为求解单个 $F(p^k)$ 找到一个 $O(\log n)$ 以内的复杂度即可。
- 例题 : [P6222 「P6156 简单题」加强版](https://www.luogu.com.cn/problem/P6222)
# 狄利克雷生成函数
对于一个数论函数， $F$ ,定义其狄利克雷生成函数为 ：
$$F(s)=\sum\limits_{i=1}\dfrac{F[i]}{i^s}$$
由于 $a^s*b^s$ 会贡献到 $(ab)^s$ ，两个数论函数的狄利克雷卷积就对应其 $\rm DGF$ 的卷积。
你可能会问为啥不用 $i^s$ 而用 $\dfrac{1}{i^s}$ ? 前者会导致级数不收敛……
本文中讨论的数论函数都是积性函数。
- 常见积性函数的 $\rm DGF$
似乎没有贝尔级数好用，先咕了。
- 狄利克雷除法
和生成函数没啥关系，只是数论函数求逆罢了。
$F*G=e$
$G[1]=1,\quad\sum\limits_{d|n}F[n/d]G[d]=0$
$F[1]G[n]+\sum\limits_{d|n,d≠n}F[n/d]G[d]=0$
$G[n]=-\sum\limits_{d|n,d≠n}F[n/d]G[d]$
复杂度 $O(n\log n)$。
当然还有更快的办法，先按照上文的方法将积性函数划分成若干个单素数积性函数，分别（多项式）求逆后，再卷积。
这样能做到 $O(n\log\log n)$。
- 狄利克雷 $\ln$
回忆 $\ln A=B\Rightarrow B=∫\dfrac{A'}{A}$ ,我们只需要再定义出导数和积分。
回忆指数函数的求导法则 $(a^x)'=a^x\ln a$
但是此处 $\ln a$ 无定义，一种广为流传的做法是，定义 $\ln n$ 为 $n$ 的质因子幂次总和。
这样就能满足 $\ln ab=\ln a+\ln b$ 的关键性质。
积分只需要定义为逆运算即可。
- 狄利克雷 $\exp$
要求 $A[1]=0$
回忆 $\exp A=B\Rightarrow \ln B=A\Rightarrow A'=\dfrac{B'}{B}\Rightarrow A'B=B'$
$\Rightarrow \sum\limits_{d|n}B[d]A'[n/d]=B'[n]$
$A[1]B[n]+\sum\limits_{d|n,d≠n}B[d]A'[n/d]=B'[n]$
$B'[n]=\sum\limits_{d|n,d≠n}B[d]A'[n/d]$
这就能 $O(n\log n)$ 递推了。