就那么一点点的生成函数与多项式

笔者对群论等数学体系的十分浅薄，如有不严谨之处请指出，会进行修改。

数列？

上过高中的朋友，应该都知道数列是什么：就是一列数嘛。

我们能有哪些方式来表示一个数列呢？有直接列举，通项公式，递推式等等…

这些方法都很好，但是都有各自的局限性。我们能否想出来一种方式，能让这种方式表示出任何的数列呢？或者说，是否能建立起数列和另一种东西的一一映射？

函数？

那可能就是函数了。对于一个数列$a_0, a_1, a_2,... a_n$，我们将其整理为一种函数：
$f(x) = a_0 + a_1x+a_2x^2+...+a_nx^n$
我们拿一个数列，“生”出了一个函数出来，这样的函数被称之为生成函数。按照上述方式生成出的函数叫普通生成函数(Ordinary Generating Function, OGF)。

为什么我们需要生成函数？我们可以通过对函数的一些基本运算，得到不同的数列。

比如说，对于数列 $1,1,1,1,...$，其生成函数为$f(x)=1+x+x^2+x^3+...$
我们可以针对这个生成函数来列出一个等式：$f(x)=xf(x)+1$。可以发现，我们通过对$f(x)$乘上$x$,来实现了式子的右移。

我们甚至可以直接写出：$f(x)=\frac{1}{1-x}$。我们用一个简单的分式，来表达出了有无穷多项的数列！这样的式子被称为生成函数的封闭形式。

可以试试看，下面的几个数列的生成函数是多少呢？

等比数列：$1,2,4,8,...$
一隔一的数列：$0,1,0,1,...$
组合数：$C_n^0,C_n^1,C_n^2,...,C_n^n$
等差数列：$0,1,2,3,...$
斐波那契数列：$1,1,2,3,5,8,...$

神奇指令 series x/(1-x-x^2) to order 20

等等，我们是不是能拿它推通项公式…

以斐波那契数列为例，通项公式为
$F(n) = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^n - \left( \frac{1 - \sqrt{5}}{2} \right)^n \right)$
因此，尽量将分式拆成等比数列形式。

试试两个生成函数相乘？

刚才提到的各种操作的内容似乎都停留在对单个生成函数的操作，我们如果将两个生成函数相乘会发生什么呢？

$F(x)=a_0+a_1x+a_2x^2+a_3x^3+...$
$G(x)=b_0+b_1x+b_2x^2+b_3x^3+...$

可以发现相乘之后，每一项的编号之和都是相同的，formally：
$c_n=\sum_{i=0}^{n}a_ib_{n-i}$
很像是把两个多项式卷起来，我们可以把它称之为卷积。在信号与系统书中，会将卷积的各种求法，实际上大同小异。

来试试推导： $1^2+2^2+3^2+...+n^2=?$

Prob: P2000 拯救世界

广义二项式定理：![[Pasted image 20250329152413.png]]

普通在哪？

刚刚提到的OGF之所以被称作OGF，是因为还有其他类型的生成函数，如指数生成函数（EGF)、Dirichlet生成函数（DGF） 等。

指数生成函数：$F(x)=a_1x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+...$由于泰勒展开而得名。
它的作用是什么？

1. 可以尝试去做一做两个指数生成函数相乘…
2. 设想一下球盒模型…

经常出现在带标号的部分组合数学问题当中。

Dirichlet生成函数：$F(s)=\frac{a_1}{1^s}+\frac{a_2}{2^s}+\frac{a_3}{3^s}+...$
继续考虑相乘的情况…

Prob:求长度为$n$的01字符串中不可分解的字符串的个数。

多项式？

对于求和式$\sum a_nx_n$，如果是有限项相加，称为多项式。我们可以理解为，我们以多项式的形式存储了一列信息。

我们有什么表示多项式的方式吗？

我们如果设多项式的最高次为n，那么不难发现，我们只要给出n个函数图像上的点，就一定可以唯一确定这个多项式。我们可以直接列出方程组，通过高斯消元得到。

当然，我们也可以使用拉格朗日插值来更快地生成多项式。原理很简单，其实和高中学过的”两点式“差不多。

$f(x)=\sum^n_{i=1}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}$
时间复杂度为$O(n^2)$，也有更快的优化方法。

![[Pasted image 20250326153502.png]]
嗯，看来确实可以唯一确定。

那实际上我们就有了一种新的表示多项式的方法——点值表示法。用几个确定的点来表示出这个多项式。

点值表示法有什么作用呢？回忆一下解析几何，可以想起：两个多项式相乘（也就是两个多项式所对应的数列相卷积），可以直接用点值相乘，如$(x,y_1) (x,y_2) \to(x, y_1y_2)$ 得到一个新多项式。

变换？

为什么能把一个数列写成生成函数的形式呢？其实可以理解为生成函数是对于这个数列的一个变换，也就是用另一种方式来表达某个东西（我们用函数来表达了一个数列）。这与信号与系统中的Z变换较为相似。

除此之外比较常用的变换，还有傅里叶变换(Fourier Transform)——将一个函数看作是各种频率的正弦函数叠加而成，每一种频率，都有其对应的振幅。那么，就可以重新以频率为自变量，振幅为因变量做出一个全新的函数。

我们如何求出一个函数的傅里叶变换呢？公式如下：
$F(\omega)=\int^{\infty}_{-\infty}f(t)e^{-i\omega t}\mathrm dt$
其中，$t$指时间。所以$f(t)$是关于时间的函数，有时间才有频率。根据欧拉公式（$e^{ix}=\cos x+i\sin x$），这其中的 $e^{-i\omega t}$ 其实就是正弦，余弦函数。我们还可以使用傅里叶反变换来把这个频率的函数给变回原来的样子：
$f(t)=\frac{1}{2\pi}\int^{\infty}_{-\infty}F(\omega)e^{-i\omega t}\mathrm dt$

傅里叶变换在信号与系统当中有着极其重要的作用，因为我们很多时候会对一个信号的频率来进行一定的处理。它可以处理连续的信号，当然也可以处理离散的信号（也就是处理我们经常会碰到的数列）。

这些东西都可以来唯一表示数列：想象为一系列正交的向量。

快速…傅里叶变换？

我们对数列进行操作，肯定是离不开卷积的。但是我们按照原方式进行卷积的复杂度是$O(n^2)$，似乎不是很能接受。
如果我们使用点值表示法，对每一个点进行乘积，时间复杂度就成了$O(n)$，似乎可以接受。但是我们对多项式求$n$个点，再使用拉格朗日插值变回多项式，这两个操作的复杂度都是$O(n^2)$，我们好像又不能接受了。有什么办法吗？

• 试试分治？
• 怎么快速求值？
• 傅里叶？
• 不想爆栈，还能优化吗？（蝶形运算）
  于是，我们就得到了快速傅里叶变换(FFT)的过程。

const double pi = acos(-1.0);

int r[4000010], n, m, l, limit = 1;
complex<double> a[4000010], b[4000010];

void FFT(complex<double> *A, int e){
    for(int i = 0; i< limit;i++){
        if(r[i] < i)swap(A[i], A[r[i]]);
    }
    for(int i = 1;i < limit;i<<=1){
        complex<double> wn(cos(pi/i), (double)e * sin(pi/i));
        int len = i<<1;
        for(int j = 0; j < limit; j+=len){
            complex<double> w(1,0);
            for(int k = 0; k<i;k++,w *= wn ){
                complex<double> x = A[j + k], y = w * A[j + i + k];
                A[j + k] = x + y;
                A[j + i + k] = x-y;
            }
        }
    }
}

//预处理
for(int i = 0;i<limit;i++){
    r[i] = ((r[i>>1]>>1) | ((i & 1) << (l-1)));
}

板子题：P1919 A*B Problem

还有什么变换？

除了FFT以外，还有快速数论变换(NTT)，快速沃尔什变换(FWT)。

快速数论变换(NTT)在算法竞赛中可能更为常见，它实际上是利用了模运算的乘方周期性，来代替了原来FFT的复数的乘方周期性。

快速沃尔什变换(FWT)解决的是是一种更为广义的卷积，卷积原先是定义在”和相同“之上的，FWT针对的卷积可以处理位运算，有的时候似乎可以用来优化状压dp？

更多，更多，更多的算法…

牛顿迭代法

如果给定一个多项式$F(x)$，如何计算$\ln F(x)，\frac{1}{F(x)},\sqrt{F(x)}$等各种各样的”函数套函数“呢？

牛顿迭代法，实际上是从一个常数开始，不断倍增，慢慢接近目标的多项式的过程。我们需要利用的公式是：

$f_{2n}(x)\equiv f_n(x)-\frac{G(x,f_n(x))}{\frac{\partial G}{\partial y} G(x,f_n(x))}$，如果给定函数为$h(x)$，操作的函数为$g(y)$，那么$G(x,y)=g(y)-h(x) =0$.

（证明过程用到了泰勒展开）

来试一试：CF438E-The Child and Binary Tree

拉格朗日反演

如果我们得知了一个生成函数的封闭形式，我们如何知道每一项的具体的值呢？

这时候就需要使用Lagrange反演了。常用的公式是：
$[x^n]F(x)=\frac{1}{n}[x^{n-1}](\frac{x}{G(x)})^n$，其中，$F(G(x))=G(F(x))=x$，也就是$F(x),G(x)$互为复合逆。

来试一试：P2767 树的数量

参考资料

浅谈多项式与生成函数 - joke3579 - 博客园
算法学习笔记 - 知乎
多项式与生成函数学习笔记 - ChroneZ - 博客园
[算法竞赛入门] 生成函数：函数与数列之间的桥梁 (蒋炎岩)