数论：生成函数

· · 个人记录

生成函数

1. 定义

任意给一个无穷序列 a_0,a_1,...a_n,...，定义 g(x)=a_0+a_1x+a_2x^2+...a_nx^n，一般认为 x\in(-1,1)，那么我们就称 g(x) 为无穷序列的生成函数。

可以发现，生成函数其实是一种映射。

然后，这里就可以变为与多项式有关的东西（FFT、NTT 警告）。

还有各种之类的高等数学，这里就不展开了。

2. 应用

一）砝码拼凑

给定三个砝码，重量分别为 a,b,c g，然后再给定需要拼凑的重量 n，问有多少种方案。

这里，我们首先可以用三个序列来分别表示三个砝码能表示的重量的方案。

以 a 为例，它的序列为 1,0,...,0,1,0,...，其中第二个 1 的位置是 a_a。对应的函数就为 f_1(x)=1+x^a。

同理，f_2(x)=1+x^b,f_3(x)=1+x^c。

我们发现，如果将这三个的函数相乘的话，其实就是我们的砝码的表示方案。

简单的证明一下：我们以前计算使用的乘法原理，其实就是我们新的多项式相乘。加法原理，其实就是新的同类项合并。

那么，将三个函数（就是多项式）相乘，就可以得到最终的方案的表示。

2）砝码拼凑（加强版）

给定三种砝码，重量分别为 a_i g，每一种砝码可以取 x_i 个（x_i=0 表示可以无穷取），然后再给定需要拼凑的重量 n，问有多少种方案。

首先，我们看：1 g 的可以取 2 个，生成函数是什么。

对应的序列应该就是 1,1,1,0,0,0,0...，对应的就是 f_1(x)=1+x+x^2。

我们再来看：2 g 的可以取无限个，生成函数是什么。

对应的序列就是 1,0,1,0,1,0,1,0,1...，对应的就是 f_2(x)=1+x^2+x^4+...。

相乘，每一项就是方案数。

3）取苹果

有 n 种不同的苹果，每种有无限个，现在要取 k 个，问方案数。

我们可以使用隔板法求，但不是今天的重点。

我们考虑对于每一个苹果来说，生成函数都是 f(x)=1+x+x^2+x^3+...。通过等比数列的性质，可以得到：f(x)=\dfrac{1}{1-x}(x\in(-1,1))。

那么，总的生成函数就是 g(x)=\dfrac{1}{(1-x)^n}。

具体怎么展开，我们暂且不讲，需要使用可以自行百度其实是我不会。

3. 例题

T1：食物

题目传送门 AcWing

这就是一个简单的生成函数。

经过一通推导，可以得到：

F(x)=\dfrac{x}{(1-x)^4}

下面的可以展开（鬼知道怎么展开）：

\begin{aligned} F(x)&=x\cdot(\sum_{n=0}^{+\infty}\binom{n+4-1}{4-1}x^n)\\&=\sum_{n=0}^{+\infty}\binom{n+3}{3}x^{n+1} \end{aligned}

那么，我们就可以直接计算了，答案就是 \binom{n+2}{3}。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 505, Mod = 1e4 + 7;
char str[N];

int main()
{
    cin >> (str + 1);
    ll n = 0;
    for (int i = 1; i <= (int)strlen(str + 1); ++ i) n = (n * 10 + str[i] - '0') % Mod;
    cout << n * (n + 1) * (n + 2) / 6 % Mod << endl;
    return 0;
}