普通生成函数

定义：\(F(x)=\sum_{n>=0}\ a_nx^n\)

加减运算

$F(x) \pm G(x)=\sum_{i>=0}\ a_ix^i \pm \sum_{j>=0} b_jx^j $
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \sum_{n>=0} (a_n \pm b_n)x^n\)
因此\(F(x) \pm G(x)\)是序列\(<a_n \pm b_n>\)的普通生成函数

乘法运算（卷积）

\(F(x)G(x)=\sum_{i>=0} a_ix^i \sum_{j>=0} b_jx^j\)
我们关注\(i+j=n\)的结果
\(F(x)G(x)=\sum_{n>=0}x^n \sum_{i=0}^{n} a_ib_{n-i}\)
因此\(F(x)G(x)\)是序列\(<\sum_{i=0}^n a_ib_{n-i}>\)的普通生成函数

运用

普通生成函数可以用来求解多重集组合数问题。

问题:有\(n\)种物品，每种物品有\(a_i\)个，问取\(m\)个物品的组合数
设从每种物品中取\(b_i\)个，对于一组选定的\(b_i\)进行组合方案数为1。所以第\(n\)种物品的生成函数为\((1+x^1+x^2+...+x^{a_n})\)即我们求对\(1\)到\(n\)所有物品的生成函数的积，输出\(x\)的指数为\(m\)的项的系数即可

例题

\(HDU-2152 \ Fruit\)
有\(n\)种水果，每种水果选购的个数在\([a_i,b_i]\)之间，问买\(m\)个水果有多少种购买方案
构造普通生成函数\((x^{a_1}+...+x^{b_1})(x^{a_2}+...+x^{b_2})...(x^{a_n}+...+x^{b_n})\)

int cala(){
    for(int i=a[1]; i<=b[1]; i++){
        C[i]=1;
    }
    for(int i=2; i<=n; i++){//枚举每个多项式
        //求x^j*x^k的系数
        for(int j=0; j<=m; j++){//求购买m个水果，枚举到m就可以
            for(int k=a[i]; k<=b[i]; k++){//新添的括号内的系数
                D[j+k]+=C[j];
            }
        }
        for(int j=0; j<=n; j++){
            C[j]=D[j];
            D[j]=0;
        }
    }
    return C[m];
}