这两天抽空看了点关于生成函数的知识，指数型和普通生成函数在组合数学中基本都学习过了，主要是狄利克雷生成函数比较新颖，遂开一篇博客做一些笔记（理解不到位之处还望指出www）
定义：
众所周知，对于一个序列 ${a_n}$ ,他的普通形式的母函数为 $\Sigma_{n \ge 0} a_nx^n$ ,指数形母函数为 $\Sigma_{n \ge 0} a_n \frac{x^n}{n!}$ ,相应的，他的DGF（Dirichlet Generating Function）也有类似的形式。定义为： $f(s) = \Sigma_{n = 1}^{\infty } \frac{a_n}{n^s} = a_1+\frac{a_2}{2^s}+\frac{a_3}{3^s}+\cdots$ .
一些性质：
既然是生成函数，那么很重要的一点就是，若已知 ${a_n}$ 的生成函数$f$ 和 ${b_n}$ 的生成函数 $g$, $fg$ 应该如何表示呢？
对于普通型生成函数，有 $fg = \Sigma_{n \ge 0}(\Sigma_{r=0}^{n}a_rb_{n-r})x^n$
而对于指数型生成函数，有 $fg = \Sigma_{n \ge 0} (\Sigma_{r+s=n} \frac{a_rb_s}{r!s!})x^n$
对于狄利克雷生成函数，我们有：
$$
\begin{equation}
\begin{split}
fg &= (a_1+\frac{a_2}{2^s}+\frac{a_3}{3^s}+\cdots)(b_1+\frac{b_2}{2^s}+\frac{b_3}{3^s}+\cdots)\\
&=(a_1b_1) + \frac{(a_1b_2+a_2b_1)}{2^s} + \frac{(a_1b_3+a_3b_1)}{3^s} + \frac{(a_1b_4+a_2b_2+a_4b_1)}{4^s} + \cdots \\
&=\Sigma_{n \ge 1} \frac{\Sigma_{d|n}a_db_{\frac{n}{d}}}{n^s}
\end{split}
\end{equation}
$$
也就是说，对于 ${a_n}$ 和 ${b_n}$ 的 DGF：$f$ 和 $g$ ，$fg$ 恰好正是 ${a_n}$ 和 ${b_n}$ 的狄利克雷卷积的DGF！这是一个很有意思的性质，并且这个性质指导了我们在遇到积性函数时，考虑DGF也许会有一些有趣的发现。
不难发现序列 ${1,1,1,\cdots}$ 的DGF是 $\Sigma_{n \ge 1} \frac{1}{n^s} = \zeta(s)$ , 即黎曼Zeta函数。而 $1(n)$ 和 $1(n)$ 的
狄利克雷卷积（$1*1$）为$d(n)$，即n的因子个数的函数。所以 $\zeta^2(s) = \Sigma\frac{d(n)}{n^s}$ .
接下来的一条很有趣(也很有用)的性质是：如果 $f(n)$ 是一个积性函数，那么：
$$
\Sigma_{n=1}^{\infty} \frac{f(n)}{n^s} = \prod_p(1+\frac{f(p)}{p^s}+\frac{f(p^2)}{p^{2s}}+\frac{f(p^3)}{p^{3s}}+\cdots)
$$
其中 $p$ 遍历全体素数。证明也比较容易，考虑积性函数的性质即可。
由此我们就能得到：
$$
\begin{equation}
\begin{split}
\zeta(s) &= \prod_p(1+\frac{1}{p^s}+\frac{1}{p^{2s}}+\cdots)\\
&= \prod_p(\frac{1}{1-p^{-s}})\\
&= \frac{1}{\prod_p(1-p^{-s})}
\end{split}
\end{equation}
$$
而由莫比乌斯函数 $\mu$ 的性质我们容易知道， $\Sigma_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \prod_p(1-\frac{1}{p^s})$，即：$\Sigma_{n=1}^{\infty} \frac{\mu(n)}{n^s} =\frac{1}{\zeta(s)}$ , 即 $\zeta$ 函数的倒数正是 $\mu$ 函数的DGF。由此我们也可以很轻快地证明莫比乌斯反演公式。
一个算是DGF应用的题？
已知积性函数 $f(x)$ 满足：$f(1)=1,f(p^e)=p^2 \ (\forall\ p\ is\ a\ prime)$ , 求其前缀和 $\Sigma_{i=1}^n f(i)$ 。（摘自Project Euler）
考虑 $f(x)$ 的DGF:
$$
\begin{equation}
\begin{split}
F(s) &= \Sigma_{n=1}^{\infty}\frac{f(n)}{n^s}\\
&= \prod_p(1+\frac{f(p)}{p^s}+\frac{f(p^2)}{p^{2s}}+\cdots)\\
&= \prod_p(1+p^2(\frac{1}{p^s}+\frac{1}{p^{2s}}+\cdots))\\
&= \prod_p(\frac{1-p^{-s}+p^{2-s}}{1-p^{-s}})\\
&=\prod_p(\frac{1-p^{-s}+p^{2-s}}{1-p^{2-s}} \frac{1-p^{2-s}}{1-p^{-s}})\\
&= \prod_p(\frac{1}{1-p^{2-s}})\prod_p (\frac{1-p^{-s}+p^{2-2s}-p^{4-2s}}{1-p^{-s}})\\
&= \zeta(s-2)\prod_p (1 + \frac{p^{2-2s}-p^{4-2s}}{1-p^{-s}})\\
&= \zeta(s-2)\prod_p(1+(p^{2}-p^{4})(p^{-2s}+p^{-3s}+\cdots))\\
&=(\Sigma_{n \ge 1}\frac{n^2}{n^s})\prod_p(1+(p^{2}-p^{4})(\frac{1}{({p^2})^{s}}+\frac{1}{({p^3})^{s}}+\cdots))
\end{split}
\end{equation}
$$
而我们要求的是这个级数 $\Sigma \frac{a_n}{n^s}$ 的 $a_n$ 的前缀和，而由之前推的式子可以得知，此时我们只需要枚举“每个质因子的幂次均大于等于2”的数（powerful number）并累加他们的贡献即可，易证明这些数的个数量级在 $O(\sqrt n)$ ，而每次累加的贡献可以用平方和公式 $O(1)$ 得到，故将总体复杂度降至了 $\sqrt n$ 。（该方法学习自PE639的Thread中第一篇post）。
