傳送陣 ?Matrix67大神的總結(jié)：跟著大神學(xué)，也不喜歡叫母函數(shù)，都稱生成函數(shù)。
在數(shù)學(xué)中，某個序列 的生成函數(shù)是一種形式冪級數(shù)，其每一項的系數(shù)可以提供關(guān)于這個序列的信息。使用生成函數(shù)解決問題的方法稱為母函數(shù)方法。
生成函數(shù)可分為很多種，包括普通生成函數(shù)、指數(shù)生成函數(shù)、L級數(shù)、貝爾級數(shù)和狄利克雷級數(shù)。對每個序列都可以寫出以上每個類型的一個生成函數(shù)。構(gòu)造生成函數(shù)的目的一般是為了解決某個特定的問題，因此選用何種生成函數(shù)視乎序列本身的特性和問題的類型。
生成函數(shù)的表示一般使用解析形式，即寫成關(guān)于某個形式變量x的形式冪級數(shù)。對冪級數(shù)的收斂半徑中的某一點，可以求母函數(shù)在這一點的級數(shù)和。但無論如何，由于母函數(shù)是形式冪級數(shù)的一種，其級數(shù)和不一定對每個x的值都存在。
具體我就不多說了，Matrix67大神blog里說得很好，我就直接上題了。
HDU1085?Holding Bin-Laden Captive!
生成函數(shù)的簡單題，分別有1,2,5面值的貨幣q1,q2,q3個，讓你求出最小不能由提供的貨幣組成的數(shù)值。由于此題很簡單，只考慮了兩種情況就行了。
Y=(1+x^2+x^3+x^4…+x^q1*1)*(1+x^2+x^4+x^6…x^q2*2)*(1+x^5+x^10+…x^q3*5)(這是母函數(shù)公式)
?
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int main()
{
int x,y,z,sum;
while(1)
{
RD(x);
RD(y);
RD(z);
if(x==0&&y==0&&z==0)
{
break;
}
if(x==0)
{
sum=1;
}
else if(x+2*y<4)
{
sum=x+2*y+1;
}
else
{
sum=x+2*y+5*z+1;
}
printf("%d\n",sum);
}
return 0;
}
?
?
HDU1171?Big Event in HDU?
這是一道典型的生成函數(shù)題型，不過也可以用dp做，題意是給出n個不同價值vi的物品，且物品數(shù)量為ci，讓你將總的價值分為最相近的兩部分，且價值不同的話，價值大的在前。這就是一個生成函數(shù)模板題，建立c1[]、c2[]，然后得到系數(shù)項，從中間找非空項就行了。但是，這題的惡心之處超乎你想象，首先是判跳出，注意是n<0而不是n==-1，然后是數(shù)據(jù)范圍，5000絕對不夠，請開到100001,。已wa出翔。
?
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int c1[100001],c2[100001],num[51],val[51];
int main()
{
int n,i,j,k,sum,ans;
while(scanf("%d",&n))
{
if(n<0)
{
break;
}
sum=0;
FOR(1,n,i)//生成函數(shù)模板做法
{
scanf("%d%d",&val[i],&num[i]);
sum+=num[i]*val[i];
}
ans=sum;
sum/=2;
mem(c1,0);
mem(c2,0);
c1[0]=1;
FOR(1,n,i)
{
FOR(0,sum,j)
{
for(k=0;k<=num[i]*val[i]&&k+j<=sum;k+=val[i])//也有許多變形，要活學(xué)活用
{
c2[j+k]+=c1[j];
}
}
FOR(0,sum,j)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(i=sum;i>0;--i)//這里操作一般由題目要求什么決定
{
if(c1[i]!=0)
{
break;
}
}
printf("%d %d\n",ans-i,i);
}
return 0;
}
?
HDU1059 Dividing
首先這題并不算是一個可以用生成函數(shù)過題，應(yīng)該是一個完全背包+二進制轉(zhuǎn)化的題目，但是由于數(shù)據(jù)較水，進行一些取模運算就可以用生成函數(shù)模板運算過了，建議當做模板練手題，然后再用完全背包再過一遍。題意就是問1~6價值的硬幣分別有a1~a6個，問能否分為相等的兩部分。
?
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int a[7];
int c1[20001];
int main()
{
int i,j,k,sum,ans,f,cas=0;
while(1)
{
cas++;
f=0;
sum=0;
FOR(1,6,i)
{
scanf("%d",&a[i]);
if(a[i]==0)
{
f++;
}
a[i]%=10;//這個模10很神奇，縮小了數(shù)據(jù)量（但估計是數(shù)據(jù)水了）
sum+=a[i]*i;
}
if(f==6)
{
break;
}
ans=sum;
printf("Collection #%d:\n",cas);
if(ans%2==1)//奇數(shù)肯定不能被2整除
{
printf("Can't be divided.\n");
}
else
{
sum/=2;
mem(c1,0);
c1[0]=1;
FOR(1,6,i)
{
for(j=sum;j>=0;--j)
{
for(k=1; k<=a[i]&&k*i+j<=sum; k++)//變形
{
c1[j+k*i]|=c1[j];
}
}
}
if(c1[sum]!=0)
{
printf("Can be divided.\n");
}
else
{
printf("Can't be divided.\n");
}
}
printf("\n");
}
return 0;
}
HDU1398?Square Coins
?
這也算是一道生成函數(shù)的好題，一種與完全平方數(shù)的結(jié)合。題意很簡單，給你一個n，問你n可以由完全平方數(shù)組成的方案數(shù)。
Y=(1+x+x^2+...+x^n)*(1+x^2+x^4+...)*...
?
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 1000000007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
int c1[301],c2[301];
int main()
{
int n,i,j,k;
while(1)
{
RD(n);
if(n==0)
{
break;
}
FOR(0,n,i)
{
c1[i]=1;
c2[i]=0;
}
for(i=2;i*i<=n;++i)//這就是為完全平方數(shù)做的準備
{
FOR(0,n,j)
{
for(k=0;k+j<=n;k+=i*i)//這里的處理，要根據(jù)情況不同變換
{
c2[k+j]+=c1[j];
}
}
FOR(0,n,j)
{
c1[j]=c2[j];
c2[j]=0;
}
}
printf("%d\n",c1[n]);
}
return 0;
}
HDU1028也是一道生成函數(shù)可以解決的題目，但我用五角數(shù)公式過了，就不深入了，可以作為練手。
?
POJ3734?Blocks
不得不說poj的這道生成函數(shù)相比上面的模板套用，模板變形題要有深度。這題可以用矩陣乘做，但今天是生成函數(shù)專題，就不像昨天那樣了。這題題意是可以用紅藍綠黃四種
給模塊涂色，且要求紅色與綠色的模塊數(shù)必須為偶數(shù)。生成函數(shù)本來就可以解決組合數(shù)學(xué)的問題，所以這題再合適不過了。
根據(jù)生成函數(shù)公式我們可以得到這樣一個式子：Y=[(1+x+x^2/2!+x^3/3!+x^4/4!...)^2]*[(1+x^2/2!+x^4/4!+...)^2]
這個式子里乘號前是藍色和黃色的方案，乘號后是紅色與綠色的方案。由于是求組合數(shù)，顏色相同時前后放置為同一種情況，所以需要除以排列數(shù)。
推導(dǎo)過程：
Y==>(由泰勒展式)1/4*e^2x*(e^x+e^(-x))^2==>1/4*(e^4x+2e^2x+1)==>(逆推導(dǎo))1/4*sigma(4^i+2*2^i)*x^i
所以系數(shù)就是1/4(4^n+2*2^n)==>(4^(n-1)+2^(n-1))，這樣就是可以直接用快速冪取模得到。。。
?
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<vector>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define FOR(a,b,i) for(i=a;i<=b;++i)
#define For(a,b,i) for(i=a;i<b;++i)
#define N 10007
using namespace std;
inline void RD(int &ret)
{
char c;
do
{
c=getchar();
}
while(c<'0'||c>'9');
ret=c-'0';
while((c=getchar())>='0'&&c<='9')
{
ret=ret*10+(c-'0');
}
}
inline void OT(int a)
{
if(a>=10)
{
OT(a/10);
}
putchar(a%10+'0');
}
__int64 p(__int64 x,__int64 y)//快速冪取模
{
__int64 res=1;
while(y>0)
{
if(y%2==1)
{
res=(res*x)%N;
}
x=(x*x)%N;
y/=2;
}
return res%N;
}
int main()
{
int t,n;
__int64 sum;
RD(t);
while(t--)
{
RD(n);
sum=(p(4,n-1)+p(2,n-1))%N;
printf("%I64d\n",sum);
}
return 0;
}
?
POJ2084?Game of Connections
卡特蘭數(shù)，由于通項公式可由生成函數(shù)得到，所以也發(fā)一道。。。
令h(0)=1,h(1)=1，catalan數(shù)滿足遞推式[1]：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (n>=2)
例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
另類遞推式[2]：
h(n)=h(n-1)*(4*n-2)/(n+1);
遞推關(guān)系的解為：
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
遞推關(guān)系的另類解為：
h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)
這題是道高精度，直接java搞了，沒難度。
?
import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;
public class Main
{
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
BigInteger sum,ans;
int n,i;
while(true)
{
n=cin.nextInt();
if(n==-1)
{
break;
}
sum=BigInteger.ONE;
ans=BigInteger.ONE;
for(i=1;i<=n;++i)
{
sum=sum.multiply(BigInteger.valueOf(i));
ans=ans.multiply(BigInteger.valueOf(2*n-i+1));
}
ans=ans.divide(sum);
ans=ans.divide(BigInteger.valueOf(n+1));
System.out.println(ans);
}
}
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
