NOI 一轮复习 VII：数学 B

本文是 NOI 一轮复习的第七篇，主要介绍了各类多项式、集合幂级数、生成函数和特殊数列的相关内容。

青蛙大队踏碎了此处的荒原。

本文将不会在联合省选 2024 前更新。

之后可能会更新集合幂级数和为了方便理解集合幂级数而写的 FFT。

基础概念

一些基本知识。

极限

这里不介绍极限的严谨定义。极限可以直接进行四则运算。根据极限的定义可以直接定义函数的极限。

我们定义自然底数 $e=\lim\limits_{n\to \infty} (1+\frac 1 n)^n=\lim\limits_{n\to \infty} (1+\frac 1 n)^{n+1}$ 。

导数与微分

在 $x_0$ 上的导数是 $x\to x_0$ 的极限。

设 $f(x),g(x)$ 均在 $x$ 处可导，那么：

$(f(x)+g(x))'=f'(x)+g'(x)$ ；
$(f(x)g(x))'=f'(x)g(x)+f(x)g'(x)$ ；
$\left(\frac{f(x)}{g(x)}\right)'=\frac{f'(x)g(x)-f(x)g'(x)}{g^2(x)}$ ；
$f(g(x))'=f'(g(x))g'(x)$ 。

积分

（待补充）

生成函数

生成函数是一种形式幂级数（它不是函数， $x$ 不是自变量而是自由元），其每一项的系数可以提供关于这个序列的信息。这是个很有用的东西，是用于刻画数列的组合工具，能够将很多复杂的组合问题赋以简洁的代数形式，考场上也会出现不需要多项式算法只用生成函数就能解决的问题。

一般地，生成函数可以表示为：

$F(x)=\sum_{i=0}^{\infty} a_i k_i(x)$

其中 $k_i(x)$ 被称之为核函数，对于普通的生成函数， $k_i(x)=x^i$ 。注意这个 $a$ 既可以是有穷序列，也可以是无穷序列。

组合对象

组合对象指要计数的对象，组合对象组成的集合叫做组合类。

将 $\{(a_1,a_2)\mid a_1\in A_1,a_2\in A_2\}$ 称为 $A_1,A_2$ 的笛卡尔积（又称直积），记作 $A_1\times A_2$ 。

普通生成函数（OGF）

普通生成函数的核函数为 $k_n(x)=x^n$ 。实际上，普通生成函数的系数就是序列 $a$ 的通项公式。

对于 OGF $F(x)$ ， $x$ 是自由元，因此没有实际意义，只是一个占位符， $x_i$ 用来代表它是第 $i$ 个占位符， $F[i]$ 可以表示 $F(x)$ 的第 $i$ 次项系数，简称 $i$ 次项， $0$ 次项称为常数项。

为了方便提取其中某一项的系数，有 $[x^i]F(x)=F[i]$ 。

生成函数中的求和符号并不是无穷项求和，它只是一个记号，代表的是序列。两个生成函数 $F(x),G(x)$ 相等当且仅当 $\forall i\in\mathbb{N}, F[i]=G[i]$ 。

对于序列 $a$ ，如果从某一项开始它后面都是 $0$ ，那么可以认为它是一个有穷序列。如果它是有穷的，那么它的生成函数是一个有穷幂级数，否则是无穷幂级数。

考虑两个序列 $a,b$ 的普通生成函数 $F(x),G(x)$ ，那么它们的加减法和乘法运算是跟多项式一样的。因此对于生成函数 $F(x),G(x)$ ，有：

$F(x)\pm G(x)=\sum_{n}(a_n\pm b_n)x^n,\\ \begin{aligned} F(x)G(x)&=\sum_{n}x^n\sum_{i=0}^n a_i b_{n-i}\\ &=\sum_{i}\sum_j F[i]G[j]x^{ij} \end{aligned}$

因此 $F(x)\pm G(x)$ 是序列 $\left<a_n\pm b_n\right>$ 的普通生成函数， $F(x)G(x)$ 是序列 $\left<\sum_{i=0}^n a_i b_{n-i}\right>$ 的普通生成函数。

可以发现，加法代表不相交集合的并，乘法代表笛卡尔积。

对于幂次运算， $F(x)$ 的 $n$ 次幂记作 $F^n(x)$ ，特别地， $F^0(x)=1$ 。

对 $F(x)$ 的 $n$ 次幂提取 $m$ 次项系数，可以记 $F^n[m]$ 为：

$F^n[m]=[x^m]F^n(x)$

形式幂级数的生成函数不一定好算，有时会将其转换为封闭形式。

比如说 $\left<1,1,\cdots\right>$ 的普通生成函数为 $F(x)=\sum_{n\ge 0}x^n$ ，发现 $F(x)x+1=F(x)$ ，因此得到 $F(x)=\cfrac{1}{1-x}$ ，这就是生成函数的封闭形式。

比如说， $F(x)=\sum_{n=0}^{\infty} n=\cfrac 1{1-x}$ 。作为练习，可以看一下接下来这几个题：

写出 $a=\left<0,1,1,\cdots \right>$ 的生成函数。

有 $F(x)=\sum_{n\ge 1}x^n$ ，因此 $F(x)x+x=F(x)\Rightarrow F(x)=\cfrac{x}{1-x}$ 。

写出 $a=\left<1,0,1,0,1,0\cdots \right>$ 的生成函数。

有 $F(x)=\sum_{n\ge 0} x^{2n}=\sum_{n\ge 0} (x^{2})^n$ ，因此 $F(x)x^2+1=F(x)\Rightarrow F(x) = \cfrac{1}{1-x^2}$ 。

写出序列 $a_n=\dbinom{m}{n}$ 的生成函数（ $m$ 是常数， $n\ge 0$ ）。

$\begin{aligned} F(x)&=\sum_{n\ge 0}\binom{m}{n}x^n\\ &=(1+x)^m \end{aligned}$

写出 $a=\left<1,2,3,4,5,6\cdots \right>$ 的生成函数。

$\begin{aligned} F(x)&=\sum_{n\ge 0}nx^{n-1}\\ &=\sum_{n\ge 0} (x^n)'\\ &=\left(\frac{1}{1-x}\right)'\\ &=\frac{1}{(1-x)^2} \end{aligned}$

可以发现求一个序列的前缀和的生成函数只需要乘上 $\cfrac{1}{1-x}$ ，求差分只需要乘上 $1-x$ 。

实际上我们有：

$\frac{1}{(1-x)^{n+1}}=\sum_{i}\binom{n+i}{n}x^i$

为什么呢？当 $n=1$ 时，原式成立；当 $n>1$ 时，有：

$\begin{aligned} \frac{1}{(1-x)^{n+1}}&=\frac{1}{1-x}\frac{1}{(1-x)^{n}}\\ &=\sum_{i}x^i\sum_{i}\binom{n+i-1}{n-1}x^i\\ &=\sum_{i}x^i\sum_{j=0}^i\binom{n+j-1}{j}\\ &=\sum_{i}\binom{n+i}{n}x^i \end{aligned}$

它还可以说明一个问题：如果 $f(x)$ 是关于 $x$ 的 $k$ 次多项式，那么 $f(x)$ 的差分是 $k-1$ 次多项式，前缀和是 $k+1$ 次多项式。

拯救世界。对于一种召唤方式，设 $a_n$ 代表这种召唤方式选择 $n$ 个的方案数，求出序列 $a$ 的生成函数。那么两种召唤方式一共有 $n$ 块石头的选择方式就是这两个生成函数的卷积 $F$ 的第 $n$ 项系数。

一共有 $10$ 个限制条件，依次写出它们的生成函数（封闭形式），然后把它们都乘起来（求的是笛卡尔积）得到 $\cfrac{1}{(1-x)^5}$ 。转化成形式幂级数就是 $\displaystyle\sum_{i}\binom{i+4}{4}x^i$ 。因此答案是 $\dbinom{n+4}{4}$ 。

指数生成函数（EGF）

我们通常用以下方式表示指数生成函数：

$\hat F(x)=\sum_{i=0}^{\infty} \frac{a_i}{i!} x^i$

就是多除了个 $i!$ 。

OGF 只能解决无序计数问题，对于有序计数，同一个组合类中的东西是不区分的，因此通过除掉一个 $i!$ 来解决。最后再乘上 $n!$ 就是第 $n$ 项的答案。

特殊数列

我们介绍一些特殊数列。

斐波那契数列

我们有 $f_0=1,f_1=1,f_i=f_{i-1}+f_{i-2}$ 。设它的 OGF 是 $F(x)$ ，那么：

$\begin{aligned} & F(x)=xF(x)+x^2F(x)+x+0\\ \iff & F(x)=\frac {x}{1-x-x^2} \end{aligned}$

求出它的封闭形式，可以采用待定系数法，进而化为：

$F(n) = \sum_{n=0}^{\infty}\frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} x^n$

整数 lqp 拆分。答案是 $0\sim i$ 个 $F$ 的前缀和，那么答案的生成函数为 $\displaystyle G(x)=\sum_{i=0}^{\infty}F^i(x)$ 。

也就是：

$\begin{aligned} G(x)&=\frac 1 {1 - F(x)}\\ &= \frac {1-x-x^2}{1-2x - x^2}\\ &= \sum_x \frac{1}{2\sqrt{2}}[(1+\sqrt 2)^x-(1-\sqrt 2 )^x] \end{aligned}$

直接计算即可，代码。

卡特兰数

第二类斯特林数

第二类斯特林数使用 $\begin{Bmatrix}n\\ k\end{Bmatrix}$ 或者 $S_2(n,k)$ 来表示，意义是将 $1\sim n$ 的整数划分为 $k$ 个不交的无标号非空集合的方案数。显然 $\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]$ 。可以采用暴力递推法求解：

$\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$

什么意思呢？将第 $n$ 个元素放入一个新的集合有 $\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}$ 种方案，将第 $n$ 个元素插入原来任意一个集合有 $k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$ 的方案，根据加法原理可得递推式。

可能需要记住一些第二类斯特林数（就比如说，一个出现 $1,7,6,1$ 的问题就很大能与第二类斯特林数有关）：

1
1 1
1 3 1
1 7 6 1
1 15 25 10 1
1 31 90 65 15 1
1 63 301 350 140 21 1
1 127 966 1701 1050 266 28 1
1 255 3025 7770 6951 2646 462 36 1
1 511 9330 34105 42525 22827 5880 750 45 1

第二类斯特林数的通项公式：

$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}$

不难用二项式反演去证明，令 $G_i$ 为 $n$ 个数放入 $i$ 个允许空集的有标号集合， $F_i$ 为不允许空集， $\frac{F_m}{m!}$ 即为答案。

第一类斯特林数

称之为斯特林轮换数，记作 $\begin{bmatrix}n\\ k\end{bmatrix},S_1(n,k)$ ，表示将 $1\sim n$ 的整数划分为 $k$ 个互不区分的非空轮换方案数。

一个轮换是指一个首尾相接的环形排列，两个可以通过旋转而互相得到的轮换是等价的。

第一类斯特林数的递推式：

$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$

前者是将 $n$ 放在一个单独的轮换中，后者是将其放入一个现有的轮换中。

这个玩意没有实用的通项公式。

题车

刷基础 1

一些基础题。

[CF715E] Complete the Permutations

Portal.

边可以分为四种类型， $a\rightarrow b,a\rightarrow 0,0\rightarrow b,0\rightarrow 0$ 。

记后三种边的数量为 $n_1,n_2,m$ 。 $a\rightarrow 0$ 边有两种选择，融进 $0\rightarrow 0$ ，或者自我合并。方案数是：

$F_1[k]=\sum\limits_{i=k}^{n_1}\dbinom{n_1}{i}\begin{bmatrix}i\\k\end{bmatrix}(n_1+m-i-1)^{\underline{n_1-i}}$

$F_3$ 直接算第一类斯特林数，然后可以全排列 $m$ 。暴力卷即可。代码。