Butteruni Blog
0%

生成函数基础

发表于 更新于 分类于

本文为作者对生成函数相关知识的整理

引入

数列递推

以经典的斐波那契数列为例，定义 表示斐波那契数列的第 个项，我们有 从而可以通过线性递推的方式在 的时间复杂度内求出 。

然而，线性递推的方式虽然直观，但在 较大的情况下显然不能满足我们对效率的追求。聪明的读者可能会采用特征根法求出斐波那契数列的通项公式 从而 求解。显然，当数列仅存在二阶线性递推时特征根法能发挥很好的效果（等价于求解一个一元二次方程），可如果数列存在三阶甚至更高阶递推关系时特征根法则会失去它的效用（高阶方程不存在求根公式），为此我们需要一个新的数学工具来帮助我们解决这类问题。

定义

定义生成函数 ，此时 为 数列 的母函数，对 的操作可以等价于对整个数列的操作。如果能以闭形式表达 ，那么数列 的第 项即为 在该形式下进行展开后 前的系数。

实践

对于斐波那契数列 ，其生成函数 不难发现

从而得到 ，于是求数列通项 就转换成为求函数 展开后 前的系数。

因此有 将上述式子进行泰勒展开后即可得到通项 ，结果与特征根求出来的相同。

计算

常见生成函数及其对应数列

基础操作

应用

除了处理数列递推问题，生成函数实际上广泛地在信息学竞赛中用作处理排列组合和多项式相关问题。这里主要谈论前者。

给定集合S{1,1,1,1,1,2,2,2,3,3,3,3} ，问从中选出4个数组成的不同集合有多少个

可以发现 中不同元素个数分别为5、3、4。对每个元素都有生成函数 ，其中 表示针对当前元素，选 个所对应的不同集合的数量。显然此时 。

于是答案即为 中 前的系数。

为什么答案会是这样？我们不妨先考察只存在两种元素的情况。有公式 可知此时 前系数为 ，刚好列出了所有可能的组合。实际上根据普通生成函数的定义，使得 之后 前的系数获得类似卷积的效果，恰符合组合条件下的不重不漏，使得我们能直接通过计算系数得到答案。

例题：Link with Balls - HDU 7047 - Virtual Judge (vjudge.net)

题意：已知 个桶中存放有无穷多个小球，对于第 个桶可以拿出 个球（），对于第 个桶最多拿出 个球，问一共拿出 个球的方案数

解题：

首先对所有桶按编号奇偶分类讨论，对于第 个偶数篮子有生成函数 ，于是所有偶数篮子对答案贡献为

接下来考虑奇数篮子，类似的，对于第 个奇数篮子有生成函数 ，于是所有奇数篮子对答案贡献为

于是最终答案为 逐项消去分子分母后得到最终生成函数为

由公式 得到最终答案为 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
ll fac[N],invfac[N],inv[N];
ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < N; ++i) 
        fac[i] = (fac[i - 1] * i) % mod;
    invfac[N - 1] = qpow(fac[N - 1],mod - 2);
    for (int i = N - 2; i >= 0; --i) 
        invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
}
ll C(int n, int m)
{
    if (n < m || m <= 0) return 0;
    return (fac[n] * invfac[m] % mod)*invfac[n - m] % mod;
}
ll A(int n,int m)
{
    if(n < m || m < 0)
        return 0;
    return fac[n] * invfac[n - m] % mod;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    init();
    cin >> t;
    while(t--)
    {
        ll n,m;
        cin >> n >> m;
        cout << (C(n + m,n) - C(m - 1,n) + mod) % mod << "\n";
    }
}

指数生成函数

对于组合问题，普通生成函数便能很好解决，可对于排列问题，普通生成函数就会造成重复计算等问题。同样以集合 为例，只是把所求对象换成选 个数进行排列，显然答案不会是 个数构成的不同集合数乘上 ，而是对于不同集合分别乘上 ， 为当前集合下 各自的数目。为此我们考虑另一种思路，对于大小为 的集合计算 ，最后再乘上 即可。不难发现这其实是一个卷积的形式，因此我们把 提前到原生成函数中即可。

有新定义： ，（本文中函数头上 表示其为指数生成函数 ）由于定义发生变化，指数生成函数的常用操作也与普通生成函数不同，以下是常用的几种。 常用函数封闭形式及其对应数列 不难发现实际就是函数的麦克劳林展开

此外，由于指数生成函数的特殊性，对于 可以构造 ，从而间接求

例题1：1005 Snake (hdu.edu.cn)

题意等价于：给定 个元素，要求分成 组，每组元素大小不超过 ，若两种方案之间若存在组内元素排放顺序不同则视为不同方案，求一共有多少种方案。

解题：先假设每组元素中元素个数分别为 那么有 且

那么对于一组元素，有普通生成函数 ，一共有 组元素所以答案是 的第 项系数，等价于 的第 项系数，使用二项式展开变成 于是只计算第 项系数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 1000000;
ll fac[N + 10],invfac[N + 10];
ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) 
        fac[i] = (fac[i - 1] * i) % mod;
    invfac[N - 1] = qpow(fac[N - 1],mod - 2);
    for (int i = N - 2; i >= 0; --i) 
        invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
}
ll C(int n, int m)
{
    if (n < m || m < 0) return 0;
    return fac[n] * invfac[m] % mod*invfac[n - m] % mod;
}
ll n,m,k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n >> m >> k;
        ll ans = 0;
        for(int i = 0;i <= m;++i)
        {
            if(i & 1)
            {
                ans = ((ans - C(m,i) * C(n - i * k - 1,m - 1) % mod) % mod + mod) % mod;
            }else 
            {
                ans = (ans + C(m,i) * C(n - i * k - 1,m - 1) % mod) % mod;
            }
            if(ans < 0)
                ans += mod;
            else 
                ans %= mod;
        }
//         cout << ans << ' ';
        ans = (ans * fac[n]) % mod;
        ans = (ans * invfac[m]) % mod;
        cout << ans << '\n';
    }
    return 0;
}

由于本题元素互不相同，没有体现出指数生成函数特有的性质，于是在此补充一道例题。

例题2.

Blocks - POJ 3734 - Virtual Judge (vjudge.net)

题意：用红黄蓝绿四种颜色给n个格子染色，要求红色和绿色必须是偶数个，求方案数。对10007取模。

对于染色偶数个的情况，有指数生成函数

对于奇偶无要求时，有指数生成函数

于是最终生成函数为 (

展开后得到 ，直接将 代入计算即可，此处无需乘上 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
const ll mod = 10007;
ll fac[N],invfac[N],inv[N];
ll qpow(ll a,ll b)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)
        {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < N; ++i) 
        fac[i] = (fac[i - 1] * i) % mod;
    invfac[N - 1] = qpow(fac[N - 1],mod - 2);
    for (int i = N - 2; i >= 0; --i) 
        invfac[i] = (invfac[i + 1] * (i + 1)) % mod;
}
ll C(int n, int m)
{
    if (n < m || m <= 0) return 0;
    return (fac[n] * invfac[m] % mod)*invfac[n - m] % mod;
}
ll A(int n,int m)
{
    if(n < m || m < 0)
        return 0;
    return fac[n] * invfac[n - m] % mod;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    // init();
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        cout << ((qpow(4,n) + qpow(2,n + 1)) % mod * qpow(4,mod - 2)) % mod << "\n";
    }
}

狄利克雷生成函数有空再写

本篇参考：[算法竞赛入门] 生成函数：函数与数列之间的桥梁 (蒋炎岩)

​ Concrete Mathematics: A Foundation for Computer Science