狄利克雷相关

· · 个人记录

狄利克雷前缀和

首先需要掌握 位运算卷积(FWT)与其扩展 ,否则可能无法理解某些内容。

设 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)不优。

类似地,我们在这里暴力枚举倍数也不够优。

这是前缀和而不是本文的倍数求和,不过原理类似。

考虑每个质因数是一维,做高维前缀和(其实就是卷 I ),代码是这样的:

for(int i=1;i<=tn;i++)
    for(int j=1;j*p[i]<=n;j++)
      F[j*p[i]]+=F[j];

类似地,有约数前缀差分(其实就是卷 \mu )

for(int i=1;i<=tn;i++)
    for(int j=n/p[i];j;j--)
      F[j*p[i]]-=F[j];

以后想卷 I,\mu 的时候,这样写会比暴力狄利克雷卷积快得多,还不用筛。

约数后缀和:

for(int i=1;i<=tn;i++)
    for(int j=n/p[i];j;j--)
      F[j]+=F[j*p[i]];

约数后缀差分:

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)

形如 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]

可用于加速某些题目的预处理。

我们按照枚举倍数的传统方法计算狄利克雷卷积,复杂度是 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) 以内的复杂度即可。

狄利克雷生成函数

对于一个数论函数， 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} ? 前者会导致级数不收敛……

本文中讨论的数论函数都是积性函数。

似乎没有贝尔级数好用，先咕了。

和生成函数没啥关系，只是数论函数求逆罢了。

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 A=B\Rightarrow B=∫\dfrac{A'}{A} ,我们只需要再定义出导数和积分。

回忆指数函数的求导法则 (a^x)'=a^x\ln a

但是此处 \ln a 无定义，一种广为流传的做法是，定义 \ln n 为 n 的质因子幂次总和。

这样就能满足 \ln ab=\ln a+\ln b 的关键性质。

积分只需要定义为逆运算即可。

要求 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) 递推了。