指数型生成函数学习笔记

指数型生成函数

用于解决排列计数问题，

其生成函数形式如下：
\[g^{(e)}(x)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+...\]
因为全排列出来有重复元素，对于重复了k次的a元素，在n个数中的排列方法为\(\frac{n!}{k!}\)，然后有
\[\frac{x^{m_{1}+m_{2}+\ldots+m_{k}}}{m_{1} ! m_{2} ! \ldots m_{k} !}=\frac{x^{n}}{m_{1} ! m_{2} ! \ldots m_{k} !}=\frac{n ! x^{n}}{m_{1} ! m_{2} ! \ldots m_{k} ! n !}=\frac{n !}{m_{1} ! m_{2} ! \ldots m_{k} !} \frac{x^{n}}{n !}\]
所以每一项为
\[\frac{x^{m_{1}+m_{2}+\ldots+m_{k}}}{m_{1} ! m_{2} ! \ldots m_{k} !}\]
系数就是下面那个，就是对应的要除以的数

有一些套路公式：
\[g^{(e)}(x)=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+...=e^x\]

\[g^{(e)}(x)=1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\frac{x^4}{4!}+...e^{-x}\]

\[g^{(e)}(x)=1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+...=\frac{e^x+e^{-x}} 2\]

\[g^{(e)}(x)=x+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}+\frac{x^9}{9!}+...=\frac{e^x-e^{-x}} 2\]

\[x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+...=\ln(x+1)\]

\[g^{(e)}(x)=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}=\sin x\]

\[g^{(e)}(x)=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}=\cos x\]

\[1+\frac{a}{1!}x+\frac{a(a-1)}{2!}x^2+\frac{a(a-1)(a-2)}{3!}x^3+...=(1+x)^a\]

练习

POJ-3734

选4种颜色，总数量为n，要求有红色和绿色必须是偶数个

由于是排列问题，需要用到指数型生成函数

对于相同颜色的，我们可以放到一起讨论

列出来的式子即为：
\[g^{(e)}(x)=(1+\frac{x^2}{2!}+\frac{x^4}{4!}+...)^2*(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+...)^2=(\frac{e^x+e^{-x}} 2)*(e^x)^2\]

\[=\frac {e^{4x}+2e^{2x}+1} 4\]

由于
\[e^{ax}=\sum_{n=0}^{\infty}\frac{(ax)^n}{n!}=\sum_{n=0}^{\infty}a^n\frac{x^n}{n!}\]
即为数列\(1,a^1,a^2,a^3,...\)的指数型生成函数，

所以
\[g^{(e)}(x)=\frac 1 4+\sum_{n=0}^{\infty}\frac{4^n+2^{n+1}}{4}\frac{x^n}{n!}\]
第n项的系数为\(\frac{4^n+2^{n+1}}{4}=4^{n-1}+2^{n-1}\)

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int x=0,pos=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
    for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return pos?x:-x;
}
int T;
const int mod=10007;
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int main(){
    T=read();
    while(T--){
        int n=read();
        printf("%d\n",(ksm(4,n-1)+ksm(2,n-1))%mod);
    }
    return 0;
}

在vjudge的leaderboard上rank21

HDU1521

板子题，m^2暴力展开就行了

注意指数型生成函数求出的是下面要除的数，需要乘上\(m!\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read() {
    int x=0,pos=1;
    char ch=getchar();
    for(; !isdigit(ch); ch=getchar()) if(ch=='-') pos=0;
    for(; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return pos?x:-x;
}
const int N = 20;
double f[N];
double a[N],now[N],nex[N];
int main() {
    f[0]=1;
    for(int i=1; i<=10; i++) {
        f[i]=f[i-1]*i;
    }
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF) {
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1; i<=n; i++) {
            int x=read();
            x=min(x,m);
            memset(nex,0,sizeof(nex));
            now[0]=1;
            for(int j=1; j<=x; j++) {
                now[j]=1.0/f[j];
            }
            for(int j=0; j<=m; j++) {
                for(int k=0; k<=x; k++) {
                    if(j+k<=m) {
                        nex[j+k]+=(a[j]*now[k]);
                    }
                }
            }
            for(int j=0; j<=m; j++) {
                a[j]=nex[j];
            }
        }
        printf("%.0f\n",a[m]*f[m]);
    }
    return 0;
}