指数型生成函数学习笔记
指数型生成函数
用于解决排列计数问题，
其生成函数形式如下：
\[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;
}