生成函数全家桶

· · 个人记录

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

小学生都能看懂系列

目录

超级简单的生成函数入门教程《生成函数从入门到升天（一）》

《关于随便写点什么加上书名号都能变成轻小说标题的那件事》

本文使用四个浅显易懂的 Example 帮助大家理解生成函数的实质，并为大家深入浅出地讲解了组合数学中生成函数的相关概念，简单的应用，作为一篇入门级教程，非常的清晰易懂，相信普通的小学二年级同学都能学得会（bushi 。 生成函数的进阶内容详见 超级简单清晰的生成函数升天教程《生成函数从入门到升天（二）》（还没写完，会有的 ~ ）

0x00 生成函数

下面的定义看不懂也无所谓，学完四个 Example 就懂了 ~

任意给定一个无限长的序列 a_0,a_1,a_2,\cdots,a_n\cdots

定义 函数 g(x) = a_0x^0+a_1x^1+a_2x^2\cdots+a_nx^n+\cdots

这是一个无穷级数，我们一般设 x 的取值范围为：-1<x<1，因为显然在这个范围内，无穷级数收敛，我们就可以在 x\to ∞ 的时候得到该无穷级数的值。

我们称这个函数 g(x) 为序列的生成函数。实际上就是将方案数的序列映射称一个多项式的系数，将计数问题转化为多项式问题，这样我们就可以使用积累了很多年的解决方法远多于组合数学的多项式 / 无穷级数的方法，来求解这个问题。例如我们得到生成函数以后，我们就可以使用求极限，泰勒展开，求导积分等方法。

首先给大家带来四个生活中非常浅显易懂非常常见的 \tt Example ，看懂这四个 \tt Example 以后，再来学习生成函数的具体概念就会变得非常清晰易懂了。

由于生成函数的实质就是将组合数学里的计数问题（排列与组合）转换为生成函数问题（指数生成函数与普通生成函数），进而利用生成函数的相关技巧来解决原本很难解决的组合计数问题，所以接下来的Example我会从组合数学和生成函数两个角度来解答，所以建议读者拥有基础的小学知识，知道啥是排列数与组合数 ~

0x10 例题引入

0x11 \tt Example\ A - 01背包

我们这里一共有三个砝码，分别为 1g,2g,3g，求用这三个砝码一共能凑出来多少个不同重量，并求每个重量的组成方案。

很明显这是一个01背包问题。

我们考虑如何使用组合数学 and 生成函数的方法解决这个问题。

首先分析组合数学的解法：乘法原理

对于每一个砝码来说，都有选或者不选两种选择，所以一共会有 2\times 2\times 2=8 种选法。具体的组成方案也可以很轻松地手算出来。

对应了一个方案序列，我们用序列的下标表示重量，如 a_n 表示能凑成重量 n 的方案的数量。

a0  a1  a2  a3  a4  a5  a6
1   1   1   2   1   1   1

乘法原理 \Leftrightarrow 多项式乘法

我们使用生成函数的方法来看待这个问题：

我们首先只看第一个砝码 1g

组成 0g 有一种方案，也就是不选，组成 1g 也有一种方案，就是选。

也就是：a_0=1,a_1=1

对应的生成函数： f_1(x)=1\times x^0+1\times x^1=1+x

同理，对于第二个砝码 2g

a_0=1,a_1=0,a_2=1

对应的生成函数：

f_2(x)=1\times x^0+0\times x^1+x^2=1+x^2

第三个砝码 3g

a_0=1,a_1=0,a_2=0,a_3=1

对应的生成函数为：

f_3(x)=1\times x^0+0\times x^1+0\times x^2+1\times x^3=1+x^3

根据乘法原理，我们可以将它们乘起来

总方案数 f(x)

f(x) = f_1(x) \times f_2(x) \times f_3(x)=a_0x^0+a_1x^1+a_2x^2+\cdots+a_nx^n+\cdots$ $\ \ \ \ \ \ \ \ \ =(1+x)\times (1+x^2)\times(1+x^3)$ $\ \ \ \ \ \ \ \ \ =(1+x+x^2+x^3)(1+x^3)$ $\ \ \ \ \ \ \ \ \ =1+x+x^2+2x^3+x^4+x^5+x^6$ $\ \ \ \ \ \ \ \ \ \ \ \ \ a_0\ \ \ a_1\ \ \ \ a_2\ \ \ \ \ \ a_3\ \ \ \ \ a_4\ \ \ \ \ a_5\ \ \ \ \ a_6$ $\ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ \ \ 1\ \ \ \ \ 1\ \ \ \ \ \ \ \ 2\ \ \ \ \ \ \ 1\ \ \ \ \ \ \ 1\ \ \ \ \ \ 1 原问题 $\Leftrightarrow$ 生成函数 $\Leftrightarrow$ 多项式乘积 $\Leftrightarrow$ 每一项的系数总和即为总方案数 $\ \ \ \ \Updownarrow$（原问题分解为若干子问题） 若干子问题 $\Leftrightarrow$ 乘法原理 $\Leftrightarrow$ 子问题方案数乘积 $\Leftrightarrow$ 原问题方案数 多项式展开后的每一项 $\Leftrightarrow$ 对应原问题的一种解法 合并同类项 $\Leftrightarrow$ 次数相同的合并 $\Leftrightarrow$ 次数相同代表均为凑出 $n$ 的方案 ## 0x12 $\tt Example\ B$ - 混合背包 我们这里一共有三种砝码，分别为 $1g,2g,3g$。 其中 + $1g$ 的砝码每次组合的时候可以选择 $0$ 个，$1$ 个， $2$ 个。+ $2g$ 的砝码每次组合的时候可以选择无限个 ∞+ $1g$ 的砝码每次组合的时候可以选择 $0$ 个，$1$ 个。 求用这三种砝码凑出来 $4g$ 的方案数。 我们可以根据上面 **Example A** 的方法，构造出来生成函数们 $f_1(x) =1\times x^0+1\times x^1+1\times x^2=1+x+x^2 f_2(x) =1\times x^0+1\times x^2+1\times x^4+1\times x^6+1\times x^8+\cdots=1+x^2+x^4+x^6+\cdots

这里，由于我们取的 x ，-1<x<1，所以无穷级数收敛。

f_2(x)=\lim_{x\to∞}\cfrac{1-x^n}{1-x^2}=\cfrac{1}{1-x^2}

因为 x ，-1<x<1，x 是一个分数，可以看作 x=\cfrac{1}{t}，很明显，分数的次幂越来越小，所以 \lim_{x\to∞} x^n=0

当然，学过高数的一定都会，我的高数已经忘完了 ~

f_3(x)=1+x^3 f(x)=f_1(x)\times f_2(x) \times f_3(x)$ $f(x)=(1+x+x^2)(1+x^2+x^4+x^6+\cdots)(1+x^3)

凑成 4g 的方案数就是 x^4 的系数

x^4=\left\{ \begin{aligned} 1\times x^4\times 1 \\ x\times 1\times x^3 & \ \ =3 \\ x^2\times x^3\times 1 \end{aligned} \right.

0x13 \tt Example\ C - apple

我们手里现在有 n 种不同的 apple ，每种 apple 都有无限个，问让我们选出 k-1 个 apple 的方案数是多少。

因为每一种 apple 都有无限个，也就是说每一种都可以选择 1,2,3,4,\cdots,n,\cdots 个

即：

x_1+x_2+\cdots+x_n=k,\ x_i\geq 0$ 其中 $x$ 的下标代表着第几种 apple，取值代表这一种 apple 选择的个数，所以可以为 $0

这里可以使用经典的隔板法，但是隔板法要求 x_i\geq 1 ，所以我们设 x_i'=x_i+1，x_i=x_i'-1

代入后等式就变成了

x_1'+x_2'+\cdots+x_n'=k+n,\ x_i'\geq 1

这样我们就可以看作一共有 k+n 个小球，我们在小球的间隙里，放置 n-1 个隔板，把这 k+n 个小球隔开，分为 n 块（因为每一块之间至少有一个小球，所以才必须要求 x_i\geq 1），从前往后，依次对应 x_1',x_2',\cdots x_n 所分配的小球的个数，即为当前的方案，任意的一种隔板的放置方案，对应着方程组的一个解，对应着原问题的一组解。

隔板放置的总方案数就是选出 k 个 apple 的总方案，也就是原问题的总方案。

我们知道，从 k+n 个小球的间隙，也就是 k+n-1 个空隙里放置 n-1 个隔板，总放置方案数就是答案。

这实际上就是一个组合数，即

C\ _{k+n-1}^{n-1}=(^{k+n-1}_{n-1})

而我们知道

C_{m}^{n} = \frac{m!}{(m-n)! \times n!}

直接计算即可。

生成函数 \Leftrightarrow 原问题分解为若干个子问题 \Leftrightarrow 求每个子问题的生成函数 \Leftrightarrow 所有的子生成函数乘起来，系数加起来就是总方案数。

我们对于第一种 apple

f_1(x)=1+x+x^2+x^3+\cdots$ $f_1(x)=\cfrac{1-x^n}{1-x}$ $\lim_{x\to∞}f_1(x)=\cfrac{1}{1-x}

实际上对于任意一种，子问题的生成函数都是这个。

即 f_2(x)=\cfrac{1}{1-x}

所以最终 f(x)=f_1(x)\times f_2(x)\times f_3(x)\times \cdots\times f_n(x) \ \ \ \ \ \ \ \ \ =\cfrac{1}{(1-x)^n}=a_0x^0+a_1x+a_2x^2+\cdots+a_kx^k+\cdots

其中 a_k 就对应着我们上面求得的公式

a_k=C^{n-1}_{k+n-1}

0x14 \tt Example\ D - 食物

让我们直接来上手一个稍微复杂一点的实例

明明要出去旅游，要求你帮助他计算携带 N 件物品的方案数。

其中，他一共能带 8 种食物：

对于给定的 N，你要计算出选择 N 个物品的方案数并对 10007 取模。

1\le N\le10^{500}

什么鬼， 1\le N\le10^{500} ！这个怎么算？

这里就体现出我们生成函数的作用了，我们直接用组合数学的解法求的话看上去非常的头疼，所以我们直接使用生成函数试一试。

我们依次对这 8 种食物求得它们的生成函数：

这里我们就可以直接使用无穷级数等比数列的求和公式：

f_1(x)=\cfrac{a_1(1-q^n)}{1-q}=\cfrac{1\times(1-x^n)}{1-x^2} \lim_{x\to∞}f_1(x)=\cfrac{1}{1-x^2}

我们这里是为了和上面的保持同一形式，这样在最后的多项式乘法的时候方便一些。

同上，只不过这里的 a_1=x

最后

f(x)=

由上面的生成函数我们可以得到：

f(x)=f_1(x)\times f_2(x)\times\cdots f_8(x)$ $\ \ \ \ \ \ \ \ \ =\cfrac{1}{1-x^2}\times\cfrac{1-x^2}{1-x}\times\cfrac{1-x^3}{1-x}\times\cfrac{x}{1-x^2}\times\cfrac{1}{1-x^4}\times\cfrac{1-x^4}{1-x}\times\cfrac{1-x^2}{1-x}\times\cfrac{1}{1-x^3}$ $\ \ \ \ \ \ \ \ \ =\cfrac{x}{(1-x)^4}

即：f(x)=\cfrac{x}{(1-x)^4}

我们要求的答案就是凑 N 件食物的总方案数，也就是 f(x) 多项式的展开式中， x^N 的系数。我们发现这里的式子和 \tt Example\ C 的式子几乎一摸一样。我们可以再推一遍感受一下。

f(x)=\cfrac{x}{(1-x)^4}$ $\ \ \ \ \ \ \ \ \ =x(\cfrac{1}{(1-x)^4}) \ \ \ \ \ \ \ \ \ =x(C_{0+4-1}^{4-1}x^0+C_{1+4-1}^{4-1}x^1+C_{2+4-1}^{4-1}x^2+\cdots+C_{n+4-1}^{4-1}x^n+\cdots) \ \ \ \ \ \ \ \ \ =x(\sum_{n=0}^{∞}C_{n+4-1}^{4-1}x^n) \ \ \ \ \ \ \ \ \ =\sum_{n=0}^{∞}C_{n+4-1}^{4-1}x^{n+1}

推导过程：

根据 \tt Example\ C 的apple 我们知道，\cfrac{1}{(1-x)^n} 实际上就是 n 种，也就是 n 个 x。

这里的 \cfrac{1}{(1-x)^4} 可以表示为

x_1+x_2+x_3+x_4=N,x_i\ge 0

我们设 x_1'=x_1+1

即

x_1'+x_2'+x_3'+x_4'=N,x_i'\ge 1

得 C_{N-4+1}^{4-1}。

所以多项式第 N 项的系数，也就是凑 N 件物品的总方案数 ans

ans=C_{N-4+1}^{4-1}=C^{2}_{N+2}=\cfrac{(N+2)\times (N+1)\times N}{6}

最后由于 N\le10^{500}，特别大，所以我们字符串输入以后，利用秦九韶算法取模即可。

Code

const int p = 10007;
string s;
int main()
{
    cin >> s;
    ll n = 0;
    for(int i = 0; i < s.size(); ++ i) {
        n = (n * 10 + s[i] - '0') % p;
    }
    cout << n * (n + 1) * (n + 2) / 6 % p;
}

至此，相信大家都已经明白了生成函数的实质。

这时我们再给出一些正式的定义与概念理解起来就易如反掌了 ~

0x15 生成函数定义概念

生成函数（generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。 生成函数有许多不同的种类，但大多可以表示为单一的形式：

F(x)=\sum_{n}a_n k^n(x)

其中 k_n(x) 被称为核函数。不同的核函数会导出不同的生成函数，拥有不同的性质。

举个栗子：

普通生成函数： k_n(x)=x^n。 指数生成函数： k_n(x)=\dfrac{x^n}{n!}。 狄利克雷生成函数：k_n(x)=\dfrac{1}{n^x}。

另外，对于生成函数 F(x) （多项式），我们用 [k_n(x)]F(x) 来表示它的第 n 项的核函数对应的系数，也就是 a_n。

0x20 普通生成函数与指数生成函数

0x21 普通生成函数

序列 a 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：

F(x)=\sum_{n}a_n x^n

其中 a 既可以是有穷序列，也可以是无穷序列。常见的几个例子（假设 a 以 0 为起点，也就是 x^0 对应组合数学里就是啥都不选的方案）

换句话说，如果序列 a 有通项公式，那么它的普通生成函数的系数就是通项公式。

0x22 指数生成函数

上面简单介绍了一下普通生成函数，发现我上面举的四个例题都是组合计数问题，也就是转化为普通生成函数。但是别忘了排列组合，还有排列。而接下来我们要来探究的指数生成函数就是用来解决排列类问题的。

有 $n$ 种物品，并且知道每种物品的数量。要求从中选出 $m$ 件物品的**排列数**。例如有两种物品 $A,B$，并且数量都是 $1$，从中选 $2$ 件物品，则排列有"$AB$","$BA$"两种。 这里把问题简化：有三种物品，分别有 $3,2,3$ 个，问拿出 $4$ 个进行排列（$\{1123\},\{3211\}$算不同方案）的方案数是多少? 这里求的是排列数，也就是顺序不一样是两种方案。 首先介绍一下多重集的排列组合问题 + **多重集的排列组合问题：**[1](#fn1) 集合的概念是唯一性。多重集的特点就是不唯一性。也就是同一种元素可以在多重集里面多次出现。 设多重集合 $S = \{ n_1 \times a_1, n_2 \times a_2, \cdots, n_k \times a_k \},N = n_1 + n_2 + \cdots+ n_k$, 即集合 $S$ 中含有 $n_1$ 个元素 $a_1$， $n_2$ 个元素 $a_2$，$\cdots$ ，$n_k$ 个元素 $a_k$，$n_i$ 被称为元素 $a_i$ 的重数，$k$ 成为多重集合的类别数。 + **多重集的排列数问题：** 在 $S$ 中任选 $r$ 个元素的排列称为 $S$ 的 $r$ 排列，当 $r = n$ 时，有公式 $P(N; n_1\times a_1, n_2\times a_2, \cdots, n_k\times a_k) = \cfrac{N!}{n_1! \times n_2! \times \cdots\times n_k}

假设多重集一共有 N 个元素。那么对这 N 个元素全排列，除掉相同元素的全排列的积即可。其实就是先把所有可能，也就是全排列处理出来，然后相同元素可以随意互换位置，按乘法原理除掉就行。

在 S 中任选 r 个元素的组合称为 S 的 r 组合，当 \forall i ,r\le n_i 时，有公式 C(n; n_1\times a_1, n_2\times a_2, \cdots, n_k\times a_k) = C(k+r-1, r)

由公式可以看出多重集合的组合只与类别数 k 和选取的元素 r 有关，与总数无关。

我们可以由此得到一个解决思路：先把所有组合的方案求出来，然后再对每一个方案分别计算排列数，最后再加起来即可。

我们先求组合数的生成函数：

x_1x_3^3+x_2x_3^3+x_1^2x_3^2+x_1x_2x_3^2+x_2^2x_3^2+x_1^3x_3+x_1^2x_2x_3+x_1x_2^2x_3+x_1^3x_3+x_1^2x_2^2

对于序列 \{a_0,a_1,a_2, ...\} ，函数 G_e(x)=a_0+\frac{a_1}{1!}x+\frac{a_2}{2!}x^2+...+\frac{a_k}{k!}x^k+...称为序列 \{a_0,a_1,a_2, ...\}对应的指数母函数。

指数型母函数可以理解为：对于 \frac{x^i}{j!} 表示在一个方案中某个元素出现了 j 次，而在不同的位置中的 j 次出现是相同的，所以在排列计算总数时，只应算作一次，由排列组合的知识知道，最后的结果应该除以 j!

指数型母函数在使用过程中，一般会用到高等数学中的 e^x 的泰勒展开式：

e^x=\sum_{n=0}^\infty \frac{x^n}{n!}=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...+\frac{x^n}{n!}+...

因此，指数型母函数可以简化为：

G_e(x)=b_0+b_1*\frac{x}{1!}+b_2*\frac{x^2}{2!}+b_3*\frac{x^3}{3!}+...

其中，b_i 是所需的结果。

应用

指数型母函数常用于求多重排列数，即：有 n 种物品，已知每种物品的数量为 k_1,k_2,...,k_n 个，求从中选出 m 件物品的排列数。

对于 n 个元素，其中 a_0,a_1,a_2, ...,a_n 互不相同，进行全排列，可得 n! 个不同的排列。

若其中某个元素 a_i 重复了 n_i 次，那么全排列出来的必然有重复元素，而其中真正不同的排列数应为：\frac{n!}{n_i!}，即重复度为 ni!

同理，a_1 重复了 n_1 次，a_2 重复了 n_2 次，...，a_k 重复了 n_k 次 (n_1+n_2+...+n_k=n)

因此，对这样的 n 个元素进行全排列，可得到不同的排列个数实际上为：\cfrac{n!}{n_1!n_2!...n_k!}

若只对其中的 r 个元素进行全排列，就用到了指数型母函数：

构造母函数：

G(x)=(1+ \frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x_{k_1}}{k_1!})(1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x_{k_2}}{k_2!})...(1+\frac{x}{1!}+\frac{x^2}{2!}+...+\frac{x_{k_n}}{k_n!})

化简得：

G(x)=a_0+a_1x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+...+\frac{a_p}{p!}x^p

其中 p=k_1+k_2+...+k_n，a_i为选出 i 个物品的排列方法数

注：若题中有限定条件，只需将第 i 项出现的列在第 i 项的式子中，未出现的不用列入

例如：物品 i 出现的次数为非 0 偶数，则原式改为：...*(\frac{x^2}{2!}+\frac{x^4}{4!}+...+\frac{x^{ki}}{k_i!})*...

0x30 生成函数常用公式

普通型生成函数：

单下标序列普通型生成函数

A(x)=\displaystyle\sum_{n=0}^{\infty}a_nx^n

双下标序列普通型生成函数

A(x_1,x_2)=\displaystyle\sum_{n=0}^{\infty}a_{(n,m)}x_1^nx_2^m

普通型生成函数常用公式

\frac{1}{1 - x} = \sum\limits_{i = 0}^{\infty} x^i ln(1 + x) = \sum\limits_{i = 0}^{\infty} (-1)^{i} \frac{x^{i + 1}}{i + 1}

​

(1 + x)^{a} = \sum\limits_{i = 0}^{\infty} a^{\underline{i}}\frac{x^i}{i!} sin(x) = \sum\limits_{i = 0}^{\infty} (-1)^{i}\frac{x^{2i + 1}}{(2i + 1)!} cos(x) = \sum\limits_{i = 0}^{\infty} (-1)^{i}\frac{x^{2i}}{(2i)!}

指数型生成函数：

指数型生成函数用于解决排列数问题。

一般形式：

G(x) = a_0 + a_1x + a_2\frac{x^2}{2!} + a_3\frac{x^3}{3!} + a_4\frac{x^4}{4!} + \dots = \sum\limits_{i = 0}^{\infty} a_i\frac{x^i}{i!}

对于两个数列 {a_n} 和 {b_n} ，对应的指数型生成函数为：

G(x) = \sum\limits_{i = 0}^{\infty} a_i\frac{x^i}{i!} F(x) = \sum\limits_{i = 0}^{\infty} b_i\frac{x^i}{i!}

则

\begin{aligned} F(x) \times G(x) &= (\sum\limits_{i = 0}^{\infty} a_i \frac{x^i}{i!})(\sum\limits_{i = 0}^{\infty} b_i \frac{x^i}{i!}) \ &= \sum\limits_{n = 0}^{\infty} (\sum\limits_{i = 0}^{\infty} \frac{a_ix^i}{i!}\times \frac{b_{n - i}x^{n - i}}{(n - i)!})x^n \ &= \sum\limits_{n = 0}^{\infty} (\sum\limits_{i = 0}^{\infty} {n \choose i} a_i b_{n - i}) \frac{x^n}{n!} \end{aligned} F(x)⋅G(x)

显然 x^i 的系数的实际意义为：选择 i 个该物品的方案数，则 F(x) \times G(x) 的 x^i 的系数的实际意义即：从 a 和 b 中选出 i 个物品的排列数。

指数型生成函数常用公式

e^{x} = \sum\limits_{i = 0}^{\infty} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \dots + \frac{x^n}{n!} + \dots \frac{e^x + e^{-x}}{2} = \sum\limits_{i = 0}^{\infty} \frac{x^{2i}}{(2i)!} \frac{e^x - e^{-x}}{2} = \sum\limits_{i = 0}^{\infty} \frac{x^{2i + 1}}{(2i + 1)!}

二项式定理

(x+1)^n=\sum_{i=0}^{n} C_n^i~ x^i \begin{aligned}(1+x)^{-n}&=\cfrac{1}{1+x}\\ &=\sum_{i=0}^{\infty} C_{-n}^{\ i} ~ x^i\\&=\sum_{i=0}^{\infty} (-1)^i~C_{n+i-1}^{\ i}~x^i\end{aligned} (1-x)^n=\sum_{i=0}^{\infty} (-1)^i~ C_n^ {~i}~x^i (1-x)^n=\sum_{i=0}^{\infty} (-1)^i~ C_n^{~i}~x^i (x+y)^n=\sum_{i=0}^{n} C_n^{\ i} a^i·b^{n-i} \cfrac{1}{(1-x)^{n}} =\sum_{i=0}^{\infty} C_{n+i-1}^{\ i}~x^i

参考资料：

https://blog.csdn.net/aiweiluan5095/article/details/102215110?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.control