【学习笔记】数论之生成函数基础

前言

一直不是很会生成函数，但是平常遇到的数论题，很多地方都是会用到生成函数，现在正好有了时间可以搞一搞
未来说不定会补上 NTT。

FFT

（下文极有可能有一些加一减一的不合理的地方，可能以后会修修）
如果不会 FFT 那么生成函数肯定就完全做不了题了。（写过一篇不过当时根本不理解，胡写的太垃圾了）
考虑这样的一个问题：给定两个多项式 \(A(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1}\) 和 \(B(x) = b_0 + b_1x + b_2x^2 + ... + b_{m-1}x^{m-1}\)，求他们的积。
如果只是暴力地做这个问题的话需要 \(O(nm)\) 的复杂度就爆炸了。
但是我们知道，多项式除了系数表示还有点值表示，下面认为 \(n = m\) 因为显然可以用 \(0\) 补位，不妨假设 \(A\) 的点值表示为 \((x_0,A(x_0))(x_1,A(x_1))...(x_n,A(x_n))\)，\(B\) 的点值表示为 \((x_0,B(x_0))(x_1,B(x_1))...(x_n,B(x_n))\)，则设 \(C = A \times B\)，则显然可得 \(C\) 的点值表示为 \((x_0,A(x_0)B(x_0))(x_1,A(x_1)B(x_1))...(x_n,A(x_n)B(x_n))\)。
而我们知道 \(n\) 个不重的点可以唯一确定一个 \(n-1\) 次多项式，而我们 \(C\) 可以理解为一个 \(n+m\) 次多项式，所以我们只需要找到 \(n+m+1\) 个点将 \(A,B\) 均转化为点值表示然后得到 \(C\) 的点值表示，再将点值表示转化为系数表示就好了。

下面问题就转化为了给定一个多项式 \(A(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1}\) 如何求出它的点值表示。
点值表示关键就在于选择哪些点来表示，经过前人可以知道我们选择复数域上的 \(n\) 次单位根就满足十分优良的性质。

这里就要介绍一下复数域上的单位根是什么东西（不理解可以自己百度百科）：
形如 \(a + bi\) 的数就被称为复数，其中 \(i = \sqrt{-1}\)
复数相加就相当于在复平面上两个向量相加，结果为它们形成的平行四边形的对角线。
复数相乘在复平面上相当于长度相乘，俯角相加。
而单位根就要引入单位圆的概念，单位圆就是与原点距离为 \(1\) 的点构成的集合，而 \(n\) 次单位根是指的将单位圆分成 \(n\) 份后得到的 \(n\) 个向量，第 \(i\) 个向量我们记为 \(w_n^i\)，特别的 \(w_n^0 = (1,0)\)。
如下图所示为一个 \(8\) 次单位根：

根据图像我们可以得到单位根的一些性质，而且只要满足某些关键性质的数理论上都可以作为我们选择的点：

1. \(\forall i \not= j,w_n^i \not= w_n^j\)
2. \(w_n^k = \cos(\frac{2\pi}{n}k) + i\sin(\frac{2\pi}{n}k)\)
3. \(w_{n}^n = w_{n}^0 = 1\)
4. \(w_{2n}^{2k} = w_{n}^k\)
5. \(w_{n}^{k+\frac{n}{2}} = -w_{n}^k\)

上述性质的证明放在复平面上显然，就不多写了。

这个知识知道了我们就考虑开始化简给定的多项式，第一步就是按奇偶分类，设：

则 \(A(x) = A_1(x^2) + xA_2(x^2)\)，考虑将单位根带入，这里注意我们只需要枚举 \(k \in [0,\frac{n}{2}-1]\) 因为另一半可以直接在这个基础上加 \(\frac{n}{2}\) 得到。

发现这其实就是一个递归下去的子问题，递归树可知复杂度为 \(O(n \log n)\)

下面就是考虑给定一个多项式的点值表示怎么转化为系数表示，此时给定的点值表示一定为 \((w_n^i,A(w_n^i))\)，为了下文方便我们直接令 \(A(w_n^i) = y_i\)，设：

可以发现的一点是 \(a_i = C_i \times n\)，所以只要我们可以快速求出 \(C\) 我们就可以得到 \(A\) 的系数表示。
将 \(y_i\) 视为已知数，构造：

则有：

也就是说我们要求出 \(B\) 这个多项式在 \(n\) 次单位根的相反数位置的值，也就是和我们上述解决的问题多了一个负号，可以证明的是这两种方式可以套用同一个解决方法，完全等价。
现在其实就差了一个问题就是为什么 \(a_i = C_i \times n\)，下面就给出证明过程：

在内层求和中 \(j-k\) 是不会改变的，所以考虑构造：

则：

此时分类讨论。
若 \(k \not= 0\)，则：

所以：

因为 \(k \not= 0\) 所以 \(1 - w_n^k \not= 0\) 即 \(S(w_n^k) = 0\)
若 \(k = 0\)，则：

所以只有当 \(j - k = 0\) 即 \(j = k\) 时式子内部的和不为 \(0\)，也就是 \(C_k = a_k \times n\)

至此我们的 FFT 就完结撒花了（吗？）
我们会发现这是一个递归的版本实际运行效率极慢，所以要考虑换成迭代的版本。
因为我们每一次都会执行奇偶分类的操作所以我们也必须得到操作后的序列才能自底向上合并，手动模拟一下结果就如下图所示：

可以发现如果我们的 \(n\) 不为 \(2\) 的整数次幂那么这些操作就很难进行，所以就可以使用 \(0\) 补齐。将第 \(i\) 位经过操作后的位置记为 \(rev[i]\)，那么在二进制下 \(rev[i]\) 就是 \(i\) 的翻转。
具体求解 \(rev[i]\) 可以考虑将二进制下最后一位拿出来，得到剩下的位翻转的结果，然后再将最后一位放到最前面。
代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 300010;
const double PI = acos(-1);

int n, m;
struct Complex
{
    double x, y;
    Complex operator+ (const Complex& t) const
    {
        return {x + t.x, y + t.y};
    }
    Complex operator- (const Complex& t) const
    {
        return {x - t.x, y - t.y};
    }
    Complex operator* (const Complex& t) const
    {
        return {x * t.x - y * t.y, x * t.y + y * t.x};
    }
}a[N], b[N];
int rev[N], bit, tot;

void fft(Complex a[], int inv)
{
    for (int i = 0; i < tot; i ++ )
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int mid = 1; mid < tot; mid <<= 1)
    {
        auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
        for (int i = 0; i < tot; i += mid * 2)
        {
            auto wk = Complex({1, 0});
            for (int j = 0; j < mid; j ++, wk = wk * w1)
            {
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i ++ ) scanf("%lf", &a[i].x);
    for (int i = 0; i <= m; i ++ ) scanf("%lf", &b[i].x);
    while ((1 << bit) < n + m + 1) bit ++;
    tot = 1 << bit;
    for (int i = 0; i < tot; i ++ )
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    fft(a, 1), fft(b, 1);
    for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];
    fft(a, -1);
    for (int i = 0; i <= n + m; i ++ )
        printf("%d ", (int)(a[i].x / tot + 0.5));

    return 0;
}

这样我们通往生成函数的第一大关就算结束啦。

生成函数入门

本篇只讲解一些基础知识即入门所以很多地方注重理解不注重严谨，进阶的可能以后会有。

首先就是要知道什么是生成函数，以及它可以干什么。
生成函数名字很高级，其实本质它就是多项式，也就是给定一个任意序列 \(a_0,a_2,...,a_n,...\)，我们将其作为多项式的系数带入到多项式当中即变成 \(A(x) = a_0 + a_1x + \cdots a_nx^n + \cdots\)，在生成函数中我们默认 \(-1 < x < 1\)，所以其实就是一个序列和多项式的映射。
我们为什么要有这种映射呢，毕竟映射不一定可以简化问题。因为我们对于多项式的研究十分深入，可以使用各种多项式的手段解决这个问题。
对于生成函数解决的一般问题就是求方案数的问题，这类问题一般我们都会采取乘法原理什么的来解决，可以发现的是乘法原理本质上就是多项式的乘法，所以就可以转化为多项式问题了。
下面以一个例题来感受一下这个过程是什么：

题目描述：
有三个砝码重量分别为 \(1g、2g、3g\) 每个砝码可以选或者不选，询问能够组成的重量有多少种。

我们考虑将 \(a_i\) 定义为组成的重量为 \(i\) 的方案数，考虑对于每一个砝码求出其生成函数，直接将生成函数乘起来就是答案。设 \(f_i\) 表示第 \(i\) 个砝码的生成函数则有：

设 \(f(x)\) 表示最终的答案，则：

我们发现多项式乘法其实就是乘法原理，也就是我们看每个砝码究竟是选还是不选然后继续向下。
这样可能就对生成函数有点感觉了，下面再来一道题加深一下印象吧。

题目描述：
有三个砝码重量分别为 \(1g、2g、3g\)，重量为 \(1g\) 的砝码有两个，重量为 \(2g\) 的砝码有无限个，重量为 \(3g\) 的砝码有 \(1\) 个，每个砝码可以不选也可以选任意多个，询问组成重量为 \(4\) 的方案数有多少种。

依旧是上述的套路：

则：

自己枚举一下就会发现，方案数总共有 \(3\) 种。

下面就是一道生成函数的入门典题了

题目描述：
有 \(m\) 个物品，每种物品有无限个，询问从中选择 \(k\) 个的方案数有多少种。

根据我们已知的组合数学常识，可以直接插板法解决，这个问题即求

的解的个数，但是插板法只可以解决 \(x_i \ge 1\) 的情况，那么就强制每个多 \(1\) 就可以了，就转化为：

这个问题就是 \(k+m\) 个球放到 \(m\) 个盒子里面，也就是在 \(k+m\) 个球之间插 \(m-1\) 个板的方案数，答案即：

下面考虑怎么使用生成函数解决这个问题：
第一步显然是构造每一个物品的生成函数，此时的 \(a_i\) 其实就是相当于选择 \(i\) 个的方案数：

上述过程因为 \(n \to \infty\) 且 \(-1 < x < 1\)，所以 \(x^n \to 0\) 所以可以直接省略，其实上述也代表了我们生成函数里的一个重要等式：

那么我们答案的生成函数就是：

这个东西我们是不会展开的，但是我们根据组合意义推到了这个东西的展开形式：

也就是我们得到了这样一个重要的展开：

这个形式比较丑陋，换个形式就好看多了：

最后再看一道生成函数的真实题目，我们的生成函数就算是成功入门了。

题目描述：
给定 \(8\) 个物品，每个物品选择的限制如下，询问恰好选择 \(n\) 个的方案数并对 \(10007\) 取模，\(1 \le n \le 10^{500}\)
1.第一个物品必须选择偶数个
2.第二个物品选择 \(0\) 个或 \(1\) 个
3.第三个物品选择 \(0\) 个、\(1\) 个或 \(2\) 个
4.第四个物品选择奇数个
5.第五个物品选择 \(4\) 的倍数个
6.第六个物品选择 \(0\) 个、\(1\) 个、\(2\) 个或 \(3\) 个
7.第七个物品选择 \(0\) 个或 \(1\) 个
8.第八个物品选择 \(3\) 的倍数个

第一步就是将每个物品对应的生成函数求出来：

下面就是愉快的消消乐环节了：

答案就是 \(x^n\) 的系数，即：

生成函数入门完结撒花，下面就是一些更为深入和具体的东西啦。

OGF

基础知识

OGF 全称为 \(\text{oridinary generating function}\) 也就是普通生成函数，这个东西的定义与我们上文的生成函数入门里讲的是一致的。
对于一个序列 \(a_1,a_2,...,a_n,...\)，它的 OGF 即 \(f(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n + ...\)
对于生成函数我们常用的方法就是构造封闭形式，也就是上文中提到的那些看上去特别简洁的式子，这里给出几个常见的封闭形式，下文就围绕这几个封闭形式展开：

第五个式子就是二项式定理展开，其他的都在上述入门的讲解里面推导过。
除了这些还有两个不会证明的形式：

OGF 的乘法就比较有意思的（下文中 \(A[i]\) 代表第 \(i\) 项的系数）：
若 \(C = A * B\)，则有：\(C[x] = \sum_{i+j=x}A[i]B[j]\)，所以其实这个东西就是加法卷积或者叫做计数背包。
所以其实此时重新回顾一下我们入门中讲解的知识，其实就是因为 OGF 的乘法可以理解为加法卷积，所以我们可以单独构造然后乘起来就是答案。
基础知识大概就这些了，下面就是一些 OGF 的应用啦。

斐波那契数列

第一步当然就是推导大名鼎鼎的斐波那契数列的通项公式了。
斐波那契数列的定义为 \(a_0 =0,a_1 = 1,a_i = a_{i-1} + a_{i-2}(i \ge 2)\)，设它的 OGF 为 \(f(x)\)，则根据定义显然：

考虑想一些办法让 \(f(x)\) 表示自己，也就是错位一下看看：

可以显然发现当次数大于等于 \(2\) 时 \(xf(x)\) 的系数和 \(x^2f(x)\) 的系数和为 \(f(x)\) 的系数，次数小于等于 \(1\) 的项可以手动修正：

解得：

感觉这一步比较神仙，就是因为我们已知的东西根本推不出来这个，就想办法把这个转化到已知的上面即我们认为下面这个方程一定有解：

通分：

系数对应相等：

解的：

带入后把封闭形式展开就得到了斐波那契数列通项公式：

卡特兰数

卡特兰数的应用十分广泛，例如：

• 长度为 \(n\) 的仅包含小括号的合法括号序列数
• 节点个数为 \(n\) 的二叉树个数
• 在 \(n\times n\) 的网格图上，不跨越（并非不可触碰）对角线地从 \((1,1)\) 走到 \((n,n)\) 地方案数。

其部分序列为：

卡特兰数显然满足如下递推式：

其中 \(H_0 = 1,H_1 = 1\)
如果以括号序列来理解就是枚举最后块内部选择多少个。
下面就是想办法求解这个序列对应的 OGF 的封闭形式，在求之前要先引入一个新的定理，广义二项式定理：
重新定义组合数运算为：

注意的是此时 \(n\) 在复数域上，那么对于 \(a \in \mathbb{C}\) 都有：

对于卡特兰数的递推式观察会发现很像卷积，所以考虑能不能用卷积构造：

这就是一个一元二次方程，解得：

则显然应取：

根据广义二项式定理得：

考虑化简 \((\frac{1}{2})^{\underline{n}}\)：

上述推导涉及两个双阶乘的化简技巧：

考虑把我们得到的式子带入原式：

继续把这个式子带回去：

也就是成功得到了通项公式，即：

OGF 的基础部分就先告一段落了，有没有进阶部分就以后再说吧。

本栏目推荐文章
• 2024/1/13 算法笔记
• Python学习笔记
• 函数的参数类型
• 【C语言】函数的递归调用
• 【Shell基础】Bash基础与Linux三剑客
• HDP 笔记
• 学习进度笔记2
• 微软企业库Unity学习笔记(一)
• 微软企业库Unity学习笔记(二)
• NUS CS1101S：SICP JavaScript 描述：一、使用函数构建抽象

数论 函数 基础 笔记数论 函数 基础 笔记 数论 定理 函数 笔记 定理 数论 函数 笔记 数论 函数 笔记 数论20230801基础 笔记 数论 方程 基础 笔记 闭包 函数 基础 笔记 函数 基础 笔记python 数论 基础 数论 笔记