生成函数知识总结

基础知识

（1）普通生成函数：$k$ 种元素的多重集合的 $r$ 组合数（有限和无限多重集都可以）

• 数列：1，1， 1， 1， 1的生成函数，也可以表示一个因子的限制
  $$g(x)=1+x+x^2+\cdots +x^n+\cdots =\sum _{n=0}^{\infty }{x}^n=\frac{1}{1-x}$$
  
• $e_1+e_2+\cdots +e_k=n$ 的正整数解为：$C_{n+k-1}^n$。其生成函数如下
  $$g(x)=\sum _{n=0}^{\infty }{C}_{n+k-1}^n{x}^n=\frac{1}{(1-x{)}^k}$$
  

（2）指数生成函数：$k$ 种元素的多重集合的 $r$ 排列数（有限和无限多重集都可以）

（3）生成函数次数表示选择物品的次数

解题方法

对于直接可计算公式的题目：
例 生成函数为：$g(x)=(1+x+x^2+\dots )(1+x^2+x^4+\dots )(1+x^3+x^6+\dots )\dots$ 请你计算 $x^m$ 的系数

解题步骤：

练习题

HDU – 2152 Fruit （普通生成函数）

链接:http://acm.hdu.edu.cn/showproblem.php?pid=2152

题意：有 n 种水果，每种水果出现的次数在 $[a_i,b_i]$ 之间，问一共买 m 个水果有多少种购买方案？

思路：$(x^{a_1}+\cdots +x^{b_1})(x^{a_2}+\cdots +x^{b_2})\dots (x^{a_n}+\cdots +x^{b_n})$ 对这个生成函数求 $x^m$ 的系数

#include <bits/stdc++.h> using namespace std; int n,m; int a[110],b[110],C1[110],C2[110]; int solve() { 
    for(int i=0;i<=m;++i) C1[i]=C2[i]=0; for(int i=a[1];i<=b[1];++i) C1[i]=1; for(int i=2;i<=n;++i) { 
    for(int j=0;j<=m;++j) for(int k=a[i];k<=b[i];++k) C2[j+k]+=C1[j]; for(int j=0;j<=m;++j) C1[j]=C2[j],C2[j]=0; } return C1[m]; } int main() { 
    while(~scanf("%d%d",&n,&m)) { 
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]); printf("%d\n",solve()); } return 0; } 

HDU – 1521 排列组合 （指数生成函数）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1521

题意：有 n 种物品，每种物品的数量为 $a_i$ ，问取 m 个物品的排列数

思路：$(1+x+\frac{x^2}{2!}+\cdots +\frac{x^{a_1}}{a_1!})(1+x+\frac{x^2}{2!}+\cdots +\frac{x^{a_2}}{a_2!})\dots (1+x+\frac{x^2}{2!}+\cdots +\frac{x^{a_n}}{a_n!})$ 对这个式子求 $\frac{x^m}{m!}$ 的系数

#include <bits/stdc++.h> using namespace std; int n,m; int a[110],b[110]; double fac[110]; double C1[110],C2[110]; void init() { 
    fac[0]=fac[1]=1; for(int i=2;i<=100;++i) fac[i]=fac[i-1]*i; } double solve() { 
    for(int i=0;i<=m;++i) C1[i]=C2[i]=0; for(int i=0;i<=a[1];++i) C1[i]=1.0/fac[i]; for(int i=2;i<=n;++i) { 
    for(int j=0;j<=m;++j) for(int k=0;k<=a[i];++k) C2[j+k]+=C1[j]*1.0/fac[k]; for(int j=0;j<=m;++j) C1[j]=C2[j],C2[j]=0; } return C1[m]*fac[m]; } int main() { 
    init(); while(~scanf("%d%d",&n,&m)) { 
    for(int i=1;i<=n;++i) scanf("%d",&a[i]); printf("%.0lf\n",solve()); } return 0; } 

HDU – 1028 Ignatius and the Princess III （普通生成函数）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1028

题意：将整数 $n$ 拆分成正整数相加的形式，问有几种组合

思路：每一个小于 $n$ 的正整数都有可能组成。共有 $n$个因子，可以得到生成函数
$$g(x)=(1+x+x^2+\dots )(1+x^2+x^4+\dots )(1+x^3+x^6+\dots )\dots$$

$x^n$的系数就是所求的组合方式

#include <bits/stdc++.h> using namespace std; int n,c1[130],c2[130]; int solve(int m) { 
    for(int i=0; i<=m; ++i) c1[i]=c2[i]=0; for(int i=0; i<=m; ++i) c1[i]=1; for(int i=2; i<=m; ++i) { 
    for(int j=0; j<=m; ++j) for(int k=0; k<=m&&j+k<=m; k+=i) c2[j+k]+=c1[j]; for(int j=0; j<=m; ++j) c1[j]=c2[j],c2[j]=0; } return c1[m]; } int main() { 
    while(~scanf("%d",&n)) printf("%d\n",solve(n)); return 0; } 

HDU – 1085 Holding Bin-Laden Captive! （普通生成函数）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1085

题意：由面值为1、2、5的硬币不能组成的最小面值是多少。

思路：可以得到生成函数
$$g(x)=(1+x+x^2+\dots )(1+x^2+x^4+\dots )(1+x^5+x^{10})$$
从小到大遍历系数，为 0 的那一项就是不能组成的

#include <bits/stdc++.h> using namespace std; int n,a[4],b[4],c1[8005],c2[8005]; void solve(int m) { 
    for(int i=0; i<=m; ++i) c1[i]=c2[i]=0; for(int i=0; i<=a[1]; ++i) c1[i]=1; for(int i=2; i<=3; ++i) { 
    for(int j=0; j<=m; ++j) for(int k=0; k<=a[i]*b[i]&&j+k<=m; k+=b[i]) c2[j+k]+=c1[j]; for(int j=0; j<=m; ++j) c1[j]=c2[j],c2[j]=0; } } int main() { 
    while(scanf("%d%d%d",&a[1],&a[2],&a[3])&&(a[1]||a[2]||a[3])) { 
    b[2]=2,b[3]=5; int m=a[1]*1+a[2]*2+a[3]*5; solve(m); int x=1; while(x<=m&&c1[x]) x++; printf("%d\n",x); } return 0; } 

HDU – 2189 悼念512汶川大地震遇难同胞——来生一起走 （普通生成函数）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2189

题意：把n个人分成几个小组。每个小组的人数必须是素数

思路：用素数组成n，但是不知道用具体多少个素数。每一个小于等于 n 的素数都是一个因子。
可以得到生成函数：
$$g(x)=(1+x^2+x^4+x^6+\dots )(1+x^3+x^6+\dots )(1+x^5+x^{10}+\dots )$$
$x^n$的系数就是这个组合数的答案

BZOJ3028: 食物（普通生成函数 + 推导 + 欧拉降幂）

Description
明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！
我们暂且不讨论他有多么NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带N件物品的方案数。
他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等
当然，他又有一些稀奇古怪的限制：
每种食物的限制如下：
（1）承德汉堡：偶数个
（2）可乐：0个或1个
（3）鸡腿：0个，1个或2个
（4）蜜桃多：奇数个
（5）鸡块：4的倍数个
（6）包子：0个，1个，2个或3个
（7）土豆片炒肉：不超过一个。
（8）面包：3的倍数个

注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以‘个’为单位（反正是幻想嘛），只要总数加起来是N就算一种方案。因此，对于给出的N,你需要计算出方案数，并对10007取模

思路：很明显示生成函数的题，并且考虑的是组合数
可以得到生成函数：
$$g(x)=(1+x^2+\dots )(1+x)(1+x+x^2)(x+x^3+\dots )(1+x^4+x^8+\dots )(1+x+x^2+x^3)(1+x)(1+x^3+x^6+\dots )$$

$$g(x)=\frac{1}{1-x^2}(1+x)\frac{1-x^3}{1-x}x\frac{1}{1-x^2}\frac{1}{1-x^4}(\frac{1-x^4}{1-x})(1+x)\frac{1}{1-x^3}$$

$$g(x)=\frac{x}{(1-x{)}^4}=\sum _{n=0}^{\infty }{C}_{n+4-1}^3{x}^{n+1}=\sum _{n=0}^{\infty }{C}_{n+2}^3{x}^n$$
因此，答案就是 $a_n=C_{n+2}^3$

#include<bits/stdc++.h> #define ll long long using namespace std; const int Maxn=510; const int mod=10007; char s[Maxn]; ll QuickPower(ll base,ll n) { 
    ll ret=1; while(n) { 
    if(n&1) ret=(ret*base)%mod; n>>=1; base=(base*base)%mod; } return ret; } int main() { 
    scanf("%s",s+1); int n=0,len=strlen(s+1); for(int i=1;i<=len;i++) n=(n*10%mod+s[i]-'0')%mod; ll ans=n*(n+1)%mod*(n+2)%mod*QuickPower(6,mod-2)%mod; printf("%lld\n",ans); } 

2019 ICPC上海网络赛 E. Counting Sequences II （指数生成函数 + 推导）

链接：https://nanti.jisuanke.com/t/41413

题意：给定n个位置，对于每一个数$a_i$，都满足$1\le a_i\le m$，并且如果$a_i$是偶数的话，$a_i$出现的次数是偶数次，求排列的个数

思路：求的是排列，所以是指数型生成函数。在[1,m]的范围内，相当于有m个因子，每个因子分别代表对$1、2、3、4、\dots 、m$各自的限制。其中偶数有$floor(\frac{m}{2})$个，奇数有$m-floor(\frac{m}{2})$，设 $t=floor(\frac{m}{2})$，可以得到指数型生成函数
$$g(x)=(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots {)}^{m-t}(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\dots {)}^t$$
化简可得：
$$g(x)=e^{x(m-t)}(\frac{e^x+e^{-x}}{2}{)}^t=\frac{e^{x(m-t)}{\sum }_{i=0}^t{C}_t^i{e}^{x(t-i)}{e}^{-xi}}{2^t}$$
$$g(x)=\frac{{\sum }_{i=0}^t{C}_t^i{e}^{(m-2i)x}}{2^t}=\sum _{n=0}\frac{{\sum }_{i=0}^t{C}_t^i(m-2i{)}^n}{2^t}\frac{x^n}{n!}$$
因此可以得到$a_n=\frac{{\sum }_{i=0}^t{C}_t^i(m-2i{)}^n}{2^t}$，$a_n$就是答案

#include <bits/stdc++.h> #define ll long long using namespace std; const int mod=1e9+7; int t,m; ll n; int qpow(int b,int n,int mod) { 
    int res=1; while(n) { 
    if(n&1) res=1ll*res*b%mod; n>>=1; b=1ll*b*b%mod; } return res; } const int N=2e5; int fac[N+10],finv[N+10]; void init() { 
    fac[0]=fac[1]=1; for(int i=2; i<=N; ++i) fac[i]=1ll*fac[i-1]*i%mod; finv[N]=qpow(fac[N],mod-2,mod); for(int i=N-1; i>=0; --i) finv[i]=1ll*finv[i+1]*(i+1)%mod; } int C(int n,int m) { 
    return 1ll*fac[n]*finv[m]%mod*finv[n-m]%mod; } int main() { 
    init(); scanf("%d",&t); while(t--) { 
    scanf("%lld%d",&n,&m); n%=mod-1; int ans=0; int t=m/2; for(int i=0; i<=t; ++i) ans=(ans+1ll*C(t,i)*qpow(m-2*i,n,mod)%mod)%mod; ll res=qpow(2,t,mod); ans=1ll*ans*qpow(res,mod-2,mod)%mod; printf("%d\n",ans); } return 0; }