常生成函数

概述

在数学中，某个序列\(a_n\)的母函数（又称生成函数）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

序列\(a\)定义为形式幂级数有以下形式

\[F(x)=\sum_{n}a_nx^n\]

例如:

序列\(a = <1, 2, 3>\)的常生成函数是\(1 + 2x + 3x^3\)
序列\(a = <1,1,1,1...>\)的常生成函数是\(\sum_{n \ge 0}x^n\)
序列\(a = <1, 3, 5, 7...>\)的常生成函数是\(\sum_{n \ge 0}(2n+1)x^n\)

常生成函数常用于多重集选择组合问题

应用

常生成函数通常解决以下问题:

给定非负整数\(x_1,x_2,x_3...,x_k\)，求\(x_1+x_2+x_3...+x_k=n\)有多少组解

以上述问题为例，我们隐式规定了\(0\le x_i \le n\)，若我们为每个变量构造一个生成函数，则对于第i个数，它的生成函数为\(f(x)=1+x+x^2+x^3...+x^n\)，

若将所有的生成函数相乘，则\(g(x)=(1+x+x^2+...+x^n)^k\)的\(x^n\)的系数就是所求答案

这里给出几个常用替换式:

\(1+x+x^2+x^3...+x^n=\frac{1}{1-x}\)
\(\frac{1}{(1-x)^k}=\sum_{n\ge0}C_{n+k-1}^{k-1}x^n\)

例1.背包

题目链接

题目描述

tacmon准备带大家去YZ一日游，他要带很多东西，一共有以下8种：肥宅快乐水，鸡腿，鸡翅，鸡块，鸡汤，鸡蛋，大盘鸡，啤酒鸡 ...emm...真香。

他要带得东西太多了，所以你理所当然的要帮他算带N个东西的方案数啦。另外，在tacmon的眼里，所有的东西都是以“个”为单位的，而且每一种物品都有一些奇怪的限制。

tacmon最多会带1个肥宅快乐水（当然可以不带）
他也认为大盘鸡和啤酒鸡太贵了，所以这两个东西他分别最多带2个和3个
总所周知，鸡翅总是要成对出现的
tacmon认为偶数个鸡汤不好分，所以他准备带奇数个
鸡块实在太好吃了，tacmon认为一个人一定会吃4个，所以他一定会带4的倍数个鸡块
tacmon最讨厌吃鸡腿了，所以他最多带一个鸡腿
而鸡蛋，他准备带三的倍数个...

良心的tacmon觉得他的限制有点小多，所以他要好心的告诉大家，除了鸡汤，其他的东西不带也是符合要求的。

输入格式

一行一个整数N，表示tacmon要带的物品个数

输出格式

一行一个整数，即答案对\(10^9+7\)取模的结果。

数据范围

\(1 \le N \le 10^{18}\)

输入样例

输出样例

题解

本题使用容斥也能通过，这里讲解生成函数的做法，对于每一种食物，可以构造其生成函数，将八种食物累乘得到多项式\(G(x)\)，\([x^n]G(x)\)就是答案，接下来是各类食物对应生成函数的化简:

肥宅快乐水:\(1+x=\frac{1-x^2}{1-x}\)
大盘鸡:\(1+x+x^2=\frac{1-x^3}{1-x}\)
啤酒鸡:\(1+x+x^2+x^3=\frac{1-x^4}{1-x}\)
鸡翅:\(1+x^2+x^4+...=\frac{1}{1-x^2}\)
鸡汤:\(x+x^3+x^5...=\frac{x}{1-x^2}\)
鸡块:\(1+x^4+x^8...=\frac{1}{1-x^4}\)
鸡腿:\(1+x=\frac{1-x^2}{1-x}\)
鸡蛋:\(1+x^3+x^6...=\frac{1}{1-x^3}\)

因此\(G(x)=\frac{x}{(1-x)^4}=x\times\sum_{n\ge0}C_{n+3}^{3}x^n=\sum_{n\ge 1}C_{n+2}^{3}x^n\)

于是\([x^n]G(x)=C_{n+2}^{3}=\frac{(n+2)(n+1)(n)}{6}\)

注意取模就能通过本题

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int qpow(int a, int n, int mod) {
    int res = 1;
    while(n) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
signed main() {
    int n;
    cin >> n;
    cout << ((n + 2) % mod) * ((n + 1) % mod) % mod * (n % mod) % mod * qpow(6, mod - 2, mod) % mod ;
    return 0;
}

例2.Devu and Flowers

题目链接

题解

构造出每种花的生成函数\(F^i(x)=1+x+x^2...+x^{f(i)}=\frac{1-x^{f(i)+1}}{1-x}\)

累乘后\(G(x)=\prod_{i\le n}F(i)=\frac{\prod_{i\le n}(1-x^{f(i)+1})}{(1-x)^n}\)

最后答案为\([x^s]G(x)\)

若令\(A(x)=\prod_{i\le n}(1-x^{f(i)+1})\)，\(B(x)=\frac{1}{(1-x)^n}=\sum_{i\ge 0}C_{i+n-1}^{n-1}x^i\)

则答案是由\(A(x)和B(x)\)共同得出

发现n很小，因此我们可以二进制枚举\(A(x)\)的每一项，复杂度为\(O(2^n)\)，若此时枚举到的指数为\(k\)，则我们只需要求\([x^{s-k}]B(x)\)即可，容易得到这一项的值为\(C_{s-k+n-1}^{n-1}\)

对于取模且\(a,b\)很大时，我们考虑lucas定理

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7, N = 25;
int a[N];
map<int, int> mp;
int qpow(int a, int n, int mod) {
    int res = 1;
    while(n) {
        if(n & 1) res = (res % mod) * (a % mod) % mod;
        a = (a % mod) * (a % mod) % mod;
        n >>= 1;
    }
    return res;
}
int C(int a, int b, int mod) {
    int fz = 1, fm = 1;
    for(int i = 1, j = a; i <= b; i ++, j -- ) {
        fm *= (i % mod);
        fm %= mod;
        fz *= (j % mod);
        fz %= mod;
    }
    return fz * qpow(fm, mod - 2, mod) % mod;
}
int lucas(int a, int b, int mod) {
    if(a < b) return 0;
    if(a < mod && b < mod) return C(a, b, mod);
    return lucas(a % mod, b % mod, mod) * lucas(a / mod, b / mod, mod) % mod;
}
signed main() {
    int n, s;
    cin >> n >> s;
    //cout << C(10, 3) << endl << C(5, 3) << endl;
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    for(int i = 0; i < (1 << n); i ++ ) {
        int sum = 0;
        int k = 1;
        for(int j = 0; j < n; j ++ ) {
            if((i >> j) & 1) {
                sum += (a[j] + 1);
                k = -k;
            }
        }
        mp[sum] += k;
    }
    int res = 0;
    for(auto t : mp) {
        int k = t.first;
        int v = t.second;
        //cout << k << " " << v << endl;
        if(k > s) continue;
        res += v * (lucas(s - k + n - 1, n - 1, mod) % mod) % mod;
        res %= mod;
    }
    cout << ((res % mod) + mod) % mod;
    return 0;
}

例3.[CEOI2004] Sweets

题目链接

题解

本题和上一题很相似，不同的是总数是一段区间，若枚举总数则复杂度达到了\(O((b-a)n2^n)\)，显然超时，因此需要优化

\(res = \sum_{i=a}^{i=b}\sum_{j}([x^j]A(x))C_{i-j+n-1}^{n-1}\)

\(res\)的得出同上题

接下来讲讲怎么优化

变更计算顺序，将枚举i变为枚举j

\(res=\sum_{j}([x^j]A(x))\sum_{i=a}^{i=b}C_{i-j+n-1}^{n-1}\)

我们知道\(C_{a+1}^{b+1}=C_{a}^{b+1}+C_{a}^{b}\)

因此原式可化简为

\(res=\sum_{j}([x^j]A(x))(C_{b-j+n}^{n}-C_{max(a,j)-j+n-1}^{n})\)

\(max(a,j)\)是因为当\(j>a\)时并未是无意义，这一部分的答案也要被记录

接下来就是另一个问题了

本题的模数是2004，没有逆元，扩展卢卡斯定理可以做，但这里有个小技巧

我们发现\(n\)只有10，而组合数计算时的分母是\(n!\)，因此我们可以在求组合数时令分子计算时对\(2004 \times n!\)取模，最后在除以分母

这样这道题就被完美解决了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 2004, N = 15;
int n, a, b;
int ab[N];
map<int, int> mp;
int fac[N];
void init(int n) {
    fac[0] = 1;
    for(int i = 1; i <= n; i ++ ) {
        fac[i] = fac[i - 1] * i;  
    }
}

int C(int a, int b, int p) {
    int fz = 1, fm = 1;
    for(int i = 1, j = a; i <= b; i ++ , j -- ) {
        fz *= j;
        fz %= p;
    }
    //cout << fz << " " << fm << endl;
    return (fz / fac[n]) % mod;
}

signed main() {
    cin >> n >> a >> b;
    for(int i = 0; i < n; i ++ ) cin >> ab[i];
    init(n + 1);
    for(int i = 0; i < (1 << n); i ++ ) {
        int sum = 0;
        int k = 1;
        for(int j = 0; j < n; j ++ ) {
            if((i >> j) & 1) {
                sum += (ab[j] + 1);
                k = -k;
            }
        }    
        mp[sum] += k;
    }
    int res = 0;
    for(auto [k, v] : mp) {
        if(k > b) break;
        int kk = max(k, a);
        res += v % mod * (C(b - k + n, n, mod * fac[n]) - C(kk - k + n - 1, n, mod * fac[n])) % mod;
        res %= mod;
    }
    cout << (res % mod + mod) % mod << endl;
    return 0;
}