浅谈狄利克雷(Dirichlet)生成函数

前言

好长时间没写这种东西了,最近才学了一下这个东西,我好菜啊。

基本定义

首先不知道狄利克雷卷积的可以先看这里
狄利克雷生成函数是为了表示狄利克雷卷积而诞生的生成函数。对于一个数列$\lbrace f_i \rbrace$
定义其狄利克雷生成函数为:
$$F_D(x)=\displaystyle\sum_{i\ge 1} \frac{f_i}{i^x}$$
(由于作者太懒,本文以类似方式直接定义狄利克雷生成函数,后文不作解释。)
显然可以发现
$$H_D(x)=F_D(x)G_D(x)\Rightarrow h_i=\displaystyle\sum_{j|i} f_jg_{\frac{i}{j}}\tag{1}$$
至于为什么是$\frac{1}{i^x}$,而不是$i^x$,这是因为后者可能不收敛。

狄利克雷生成函数基本运算

我们不妨令所有操作都是求出狄利克雷生成函数的前$n$项。

乘法

根据式(1)暴力求解,时间复杂度是调和级数$\Theta(n\ln n)$

乘法逆与除法

根据式(1)可得:
$$f_i=\frac{h_i-\displaystyle\sum_{j|i\& j\not= i}f_j g{\frac{i}{j}}}{g_1}\tag{2}$$
这个式子在$g_1=0$的时候没法做,在$g_1=0$时不存在乘法逆,除法可能无解也可能解不唯一,本文不讨论。
所以我们能在$g_1\not =0$的情况下用$\Theta(n\lg n)$的时间内求出乘法逆或除法。

求导

$$F_D'(x)=\displaystyle\sum_{i\ge 1} f_i (\frac{1}{i^x})’=\displaystyle\sum_{i\ge 1} \frac{-\ln(i) f_i}{i^x}\tag{3}$$
直接暴力即可

求ln

$$\ln A_D(x)=B_D(x)\Rightarrow A_D'(x)=B_D'(x)A_D(x) \tag{4}$$
可以直接暴力,但是我们观察一下泰勒展开式:
$$\ln A_D(x)=-\displaystyle\sum_{i\ge 1} \frac{(1-A_D(x))^i}{i}\tag{5}$$
可以发现,如果$a_1=1$,那么可以发现$b_i$只会和展开式中的有限项有关,意思就是如果$A_D(x)$的系数都是有理数,那么$B_D(x)$的系数也都是有理数,而如果直接暴力的话使用了无理数,我们不能够接受。
那么有没有只使用有理数的快速做法呢?答案是有的。
根据式(4):
$$a_i\ln i=\displaystyle\sum_{j|i} b_j \ln{j} a_{\frac{i}{j}}\tag{6}$$
由于不同质数的$ln j$线性无关,而系数都是有理数,所以将不同质数拆开之后每一个质数都要满足上式。
for example:
$$a_{12}\ln 12=b_{12}a_{1}\ln{12} +b_{6}a_{2}\ln{6}+b_{4}a_{3}\ln{4}+b_{3}a_{4}\ln{3}+b_{2}a_{6}\ln{2}+b_{1}a_{12}\ln{1}$$
这也就是说:
$$a_{12}(2\ln 2+\ln 3)=b_{12} a_{1}(2\ln 2+\ln 3)+b_{6}a_{2}(\ln 2+\ln 3)+b_{4}a_{3}(2\ln 2)+b_{3}a_{4}\ln{3}+b_{2}a_{6}\ln{2}$$
$$(2a_{12}-2a_1b_{12}-a_2b_6-2a_3b_4-b_2a_6)\ln 2+(a_{12}-a_1b_{12}-a_2b_6-a_4b_3)\ln 3=0$$
$$2a_{12}-2a_1b_{12}-a_2b_6-2a_3b_4-b_2a_6=a_{12}-a_1b_{12}-a_2b_6-a_4b_3=0$$
我们设$t(i)$为i的质因数个数,formally,如果设$p_j$为第j大的质数,如果$i=\prod_{j\ge 1} p_j^{d_j}$(根据唯一分解定理,$\lbrace d_j \rbrace$唯一),那么$t(i)=\sum_{j\ge 1} d_j$
根据之前的结论,我们有:
$$a_it(i)=\displaystyle\sum_{j|i} b_j t(j) a_{\frac{i}{j}}\tag{7}$$
利用(7)式直接求解即可(注意$b_1$需要特殊处理),其中预处理$t$可以使用欧拉筛,复杂度$\Theta(n)$,其余复杂度$\Theta(n\lg n)$

求exp

将(7)式倒过来求解即可。

求k次幂

$$A_D^k(x)=e^{k\ln A_D(x)}$$
复杂度$\Theta(n\lg n)$
可以交这个题:
[loj#6713]狄利克雷 k 次根 加强版

代码

代码比较短,比正常多项式要好写。

Tagged with:

发表评论