指数生成函数

定义:\(F(x)=\sum_{n>=0}\ a_n \frac{x^n}{n!}\)

加法

\(F(x) \pm G(x)=\sum_{i>=0} a_i \frac{x^i}{i!} \pm \sum_{j>=0} \frac{x^j}{j!}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{n>=0}(a_n \pm b_n) \frac{x^n}{n!}\)

乘法（卷积）

\(F(x)G(x)=\sum_{i>=0}a_i \frac{x^i}{i!} \sum_{j>=0} b_j \frac{x^j}{j!}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{n>=0} x^n \sum_{i=0}^{n} a_ib_{n-i} \frac{1}{i!(n-i)!}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{n>=0} \frac{x^n}{n!}\sum_{i=0}^{n} \frac{n!}{i!(n-i)!}a_ib_{i-1}\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum_{n>=0} \frac{x^n}{n!} \sum C^i_na_ib_{n-i}\)

用处

多重集排列数问题

例题

\(HDU-1521\)排列组合
题意：有\(n\)种物品，每种物品有\(a_i\)个，问取\(m\)个物品的排列数
设每种物品中取\(b_i\)个，对于一组选\(b_i\)进行排列的方案数为\(\frac{m!}{b_1!b_2!b_3!...b_n!}\)
做卷积，所有满足\(b_1+b_2+...+b_n=m\)的项的系数之和再盛\(m!\)就是答案

void init(){
    fac[0]=fac[1]=1;
    for(int i=2; i<=11; i++){
        fac[i]=fac[i-1]*i;
    }
}

double cala(){
    for(int i=0; i<=a[1]; i++){
        C[i]=1.0/fak[i];
    }
    for(int i=2; i<=n; i++){//枚举括号
        //求x^j*x^k的系数
        for(int j=0; j<=m; j++){
            for(int k=0; k<=a[i]; k++){
                D[j+k]+=C[j]/fac[k];
            }
        }
        for(int j=0; j<=m; j++){
            C[j]=D[j],D[j]=0;
        }
    }
    return fac[m]*C[m];
}