生成函数（Generating Function）

某个序列 (a) 的生成函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。我们只关注系数，指数是用来构造的

普通生成函数：(F(x)=sum_{nge 0}a_nx^n)

(a_n) 可以是有穷序列也可以是无穷的。例如：

(<1,2,3>longrightarrow 1+2x+3x^2)

(<1,1,1,cdots>longrightarrow 1+x+x^2+cdots = sum_{nge 0}x^n)

(<1,2,4,8,cdots>longrightarrow 1+2x+4x^2+8x^3cdots = sum_{nge 0}2^nx^n)

加减运算

(F(x)pm G(x) = sum_{ige 0}a_ix^ipm sum_{jge 0}b_jx^j=sum_{nge 0}(a_npm b_n)x^n)

因此 (F(x)pm G(x)) 是 (<a_npm b_n>) 的普通生成函数。

乘法运算（卷积）

(F(x)G(x) = sum_{ige 0}a_ix^isum_{jge 0}b_jx^j=sum_{nge 0}x^nsum^n_{i=0}a_ib_{n-i}) （令 (i+j=n)）

因此 (F(x)G(x)) 是序列 (<sum^n_{i=0}a_ib_{n-i}>) 的普通生成函数

普通生成函数的用处：解决多重集组合数的问题。

问题：有 (n) 种物品，每种物品 (a_i) 个，问取 (m) 个物品的组合数？

设从每种物品种取 (b_i) 个，(0le b_ile a_i)，(m=sum^n_{i=1}b_i)，对于一组选定的 (b_i) 进行组合的方案数为 (1)。例如 3 个 A、1 个 B 的方案就是AAAB；取 2 个 A、2 个 B 的方案就是AABB。

构造生成函数：第 1 种物品的生成函数为 (1+x^1+x^2+cdots+x^{a_1})，第 (n) 种物品的生成函数为 (1 + x^1 + x2 + cdots + x^{a_n})。即 (prodlimits^n_{i=1}sumlimits^{a_i}_jx^j)，求 (x^m) 的系数。

注意指数即物品个数，系数即组合数。

例如，有 3 种物品，分别有 3，2，1 个，问取4 个物品的组合数？

枚举的话，有AAAB、AAAC、AABB、AABC、ABBC，5个方案。

构造：(left(1+x+x^2+x^3right)left(1+x+x^2right)(1+x)\begin{aligned}& =left(1+x+x^2+x+x^2+x^3+x^2+x^3+x^4+x^3+x^4+x^5right)(1+x) \ & =left(1+2 x+3 x^2+3 x^3+2 x^4+x^5right)(1+x) \ & =left(1+x+2 x+2 x^2+3 x^2+3 x^3+3 x^3+3 x^4+2 x^4+2 x^5+x^5+x^6right) \& =left(1+3 x+5 x^2+6 x^3+5 x^4+3 x^5+x^6right)end{aligned})

例题：HDU-2152 Fruit

int n, m;
int a[110], b[110], c[110], d[210];

int calc()
{
    memset(c,0,sizeof(c)); memset(d, 0, sizeof(d));
    for (int i= a[1]; i <= b[1]; ++i)
        c[i] =1; // 填充第一个括号
    for (int i = 2; i <= n; i++) { // n 个物品
        for (int j = 0; j <= m; j++) { // 第m个物品，后面的不用算
            for(int k = a[i]; k <= b[i]; k++) {
                d[j + k] += c[j]; //d是辅助数组，类似高精乘法。
            }
        }
        for (int j = 0; j <= m; j++) {
            c[j] = d[j];
            d[j] = 0;
        }
    }
    return C[m];
}

HDU-1085 Holding bin-Laden Captive!

面值为1,2,5的硬币分别有 (a_1,a_2,a_3) 枚，问用这些硬币不能组成的最小面值是多少？

中国剩余定理？

构造生成函数：(prod_{i=1}^{n}sum^{c_ia_i}_{j=0}x^j)，(c) 是单张面值。从小到大遍历系数，为 0 的那一项就是答案。这里的指数是面值，系数是方案。

(k) 的循环需要注意。

for(int k = 0; k <= a[i] * b[i] && j + k <= m; k += b[i]) {
    d[j + k] += c[j];
}