生成函数
定义
生成函数又叫母函数，可以看成对代数对象的形式上的处理，利用代数方法计算计数问题，另外也是无限可微函数的幂级数展开式。分为普通生成函数和指数生成函数。
普通生成函数
序列(h)的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：
[g(x) = h_0+h_1x+h_2x^2+cdots+h_nx^n+cdots
]
(h)既可以是有穷序列，也可以是无穷序列。
例：牛顿二项式定理
设(alpha)为实数，二项式系数的无穷数列
[binom{alpha}{0},binom{alpha}{1},binom{alpha}{2},cdots,binom{alpha}{n},cdots
]
的生成函数是
[(1+x)^alpha = binom{alpha}{0}+binom{alpha}{1}x+binom{alpha}{2}x^2+cdots+binom{alpha}{n}x^n+cdots
]
封闭形式
(1,1,1,1cdots)的生成函数为(F(x)=sum_{i ge 0} x^i)，可以转化为
[F(x) = frac{1}{1-x}
]
同理，等比数列(1,p,p^2,p^3,cdots)可以表示为(frac{1}{1-px})。
指数生成函数
序列(h)的指数生成函数（exponential generating function，EGF）定义为形式幂级数：
[g(x) = h_0+h_1x+h_2frac{x^2}{2!}+cdots+h_nfrac{x^n}{n!}+cdots
]
(h)既可以是有穷序列，也可以是无穷序列。
(h)的指数生成函数也可以看成({hat{h}|hat{h_i} = frac{h_i}{i!}})的普通生成函数。
例：(e^x)
(1,1,1,1cdots)的指数生成函数为
[g(x)=sum_{i=0}^{infin} frac{x^i}{i!}=e^x
]
一般地，(1,a,a^2,a^3,cdots)的指数生成函数是
[g(x)=sum_{i=0}^{infin} a^ifrac{x^i}{i!}=e^{ax}
]
用途
普通生成函数——组合
设(h_i)表示
[e_1+e_2+cdots+e_k=n
]
的非负整数解的个数。根据插板法有
[h_n=binom{n+k-1}{k-1} (n geq 0)
]
(h)的生成函数是
[g(x) = sum_{n=0}^infin binom{n+k-1}{k-1}x^n=frac{1}{(1-x)^k}
]
我们可以理解成是k个(frac{1}{1-x})乘在一起，也就是
[x^n=x^{e_1}x^{e_2}cdots x^{e^k}
]
例：[HDU2152 Fruit][https://vjudge.net/problem/HDU-2152]
答案为
[prod_{i=1}^{n} (sum_{j=a_i}^{b_i} x^j)
]
中(x^m)系数。
#include <bits/stdc++.h>
using namespace std;
const int mn=206;
int n,m,a,b,p[mn],q[mn];
int main()
{
while(scanf("%d%d",&n,&m)!=EOF) {
for(int i=0;i<=m;++i) p[i]=0;
p[0]=1;
for(int i=1;i<=n;++i) {
scanf("%d%d",&a,&b);
for(int j=0;j<=m;++j) q[j]=0;
for(int j=a;j<=b;++j)
for(int k=m-j;k>=0;--k) {
q[j+k]+=p[k];
}
for(int j=0;j<=m;++j) p[j]=q[j];
}
printf("%dn",p[m]);
}
return 0;
}
指数生成函数——排列
考虑(n)个元素的(k)排列的指数生成函数
[g^{(e)}(x) = P(n,0)+P(n,1)x+P(n,2)frac{x^2}{2!}+cdots+P(n,n)frac{x^n}{n!}
]
其中(P(n,i) = frac{n!}{(n-i)!})。我们可以发现
[g^{(e)}(x) = binom{n}{0}+binom{n}{1}x+cdots+binom{n}{n}x^n
]
是组合数的普通生成函数。
多重集的(k)排列
设多重集(S)为({n_1a_1,n_2a_2,cdots,n_ka_k})，那么其排列为
[g(x) = prod_{i=1}^k e^{n_ix}
]
例：[poj3734 Blocks][http://poj.org/problem?id=3734]
推出式子是
[g(x)=frac{e^{2n}+2e^{n}+1}{4}\
h_n = frac{4^n+2^{n+1}+[n==0]}{4}
]
#include <cstdio>
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lc nd<<1
#define rc nd<<1|1
#define lowbit(x) (x&(-x))
#define pLL pair<LL,LL>
using namespace std;
const int mod=10007;
template<typename T>
T qpow(T a,T b) {LL ans=1;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;}
const int mn=1e5+6;
int main()
{
int tests=1;scanf("%d",&tests);
while(tests--) {
int n;
scanf("%d",&n);
printf("%lldn",1ll*(qpow(4,n)+qpow(2,n+1))*qpow(4,mod-2)%mod);
}
return 0;
}
程序员灯塔
转载请注明原文链接：生成函数
转载请注明原文链接：生成函数