现在的位置: 首页 > 综合 > 正文

母函数小结

2017年11月02日 ⁄ 综合 ⁄ 共 9714字 ⁄ 字号 小 中 大 ⁄ 评论关闭

传送阵 Matrix67大神的总结：跟着大神学，也不喜欢叫母函数，都称生成函数。

在数学中，某个序列 的生成函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用生成函数解决问题的方法称为母函数方法。
生成函数可分为很多种，包括普通生成函数、指数生成函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个生成函数。构造生成函数的目的一般是为了解决某个特定的问题，因此选用何种生成函数视乎序列本身的特性和问题的类型。
生成函数的表示一般使用解析形式，即写成关于某个形式变量x的形式幂级数。对幂级数的收敛半径中的某一点，可以求母函数在这一点的级数和。但无论如何，由于母函数是形式幂级数的一种，其级数和不一定对每个x的值都存在。

具体我就不多说了，Matrix67大神blog里说得很好，我就直接上题了。

HDU1085 Holding Bin-Laden Captive!

生成函数的简单题，分别有1,2,5面值的货币q1,q2,q3个，让你求出最小不能由提供的货币组成的数值。由于此题很简单，只考虑了两种情况就行了。

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)(这是母函数公式)

[cpp] view
plaincopyprint?

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<algorithm>  
  4. #include<cstring>  
  5. #include<string>  
  6. #include<cmath>  
  7. #include<set>  
  8. #include<vector>  
  9. #include<stack>  
  10. #define mem(a,b) memset(a,b,sizeof(a))  
  11. #define FOR(a,b,i) for(i=a;i<=b;++i)  
  12. #define For(a,b,i) for(i=a;i<b;++i)  
  13. #define N 1000000007  
  14. using namespace std;  
  15. inline void RD(int &ret)  
  16. {  
  17.     char c;  
  18.     do  
  19.     {  
  20.         c=getchar();  
  21.     }  
  22.     while(c<'0'||c>'9');  
  23.     ret=c-'0';  
  24.     while((c=getchar())>='0'&&c<='9')  
  25.     {  
  26.         ret=ret*10+(c-'0');  
  27.     }  
  28. }  
  29. inline void OT(int a)  
  30. {  
  31.     if(a>=10)  
  32.     {  
  33.         OT(a/10);  
  34.     }  
  35.     putchar(a%10+'0');  
  36. }  
  37. int main()  
  38. {  
  39.     int x,y,z,sum;  
  40.     while(1)  
  41.     {  
  42.         RD(x);  
  43.         RD(y);  
  44.         RD(z);  
  45.         if(x==0&&y==0&&z==0)  
  46.         {  
  47.             break;  
  48.         }  
  49.         if(x==0)  
  50.         {  
  51.             sum=1;  
  52.         }  
  53.         else if(x+2*y<4)  
  54.         {  
  55.             sum=x+2*y+1;  
  56.         }  
  57.         else  
  58.         {  
  59.             sum=x+2*y+5*z+1;  
  60.         }  
  61.         printf("%d\n",sum);  
  62.     }  
  63.     return 0;  
  64. }  


HDU1171 Big Event in HDU 

这是一道典型的生成函数题型，不过也可以用dp做，题意是给出n个不同价值vi的物品，且物品数量为ci，让你将总的价值分为最相近的两部分，且价值不同的话，价值大的在前。这就是一个生成函数模板题，建立c1[]、c2[]，然后得到系数项，从中间找非空项就行了。但是，这题的恶心之处超乎你想象，首先是判跳出，注意是n<0而不是n==-1，然后是数据范围，5000绝对不够，请开到100001,。已wa出翔。

[cpp] view
plaincopyprint?

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<algorithm>  
  4. #include<cstring>  
  5. #include<string>  
  6. #include<cmath>  
  7. #include<set>  
  8. #include<vector>  
  9. #include<stack>  
  10. #define mem(a,b) memset(a,b,sizeof(a))  
  11. #define FOR(a,b,i) for(i=a;i<=b;++i)  
  12. #define For(a,b,i) for(i=a;i<b;++i)  
  13. #define N 1000000007  
  14. using namespace std;  
  15. inline void RD(int &ret)  
  16. {  
  17.     char c;  
  18.     do  
  19.     {  
  20.         c=getchar();  
  21.     }  
  22.     while(c<'0'||c>'9');  
  23.     ret=c-'0';  
  24.     while((c=getchar())>='0'&&c<='9')  
  25.     {  
  26.         ret=ret*10+(c-'0');  
  27.     }  
  28. }  
  29. inline void OT(int a)  
  30. {  
  31.     if(a>=10)  
  32.     {  
  33.         OT(a/10);  
  34.     }  
  35.     putchar(a%10+'0');  
  36. }  
  37. int c1[100001],c2[100001],num[51],val[51];  
  38. int main()  
  39. {  
  40.     int n,i,j,k,sum,ans;  
  41.     while(scanf("%d",&n))  
  42.     {  
  43.         if(n<0)  
  44.         {  
  45.             break;  
  46.         }  
  47.         sum=0;  
  48.         FOR(1,n,i)//生成函数模板做法  
  49.         {  
  50.             scanf("%d%d",&val[i],&num[i]);  
  51.             sum+=num[i]*val[i];  
  52.         }  
  53.         ans=sum;  
  54.         sum/=2;  
  55.         mem(c1,0);  
  56.         mem(c2,0);  
  57.         c1[0]=1;  
  58.         FOR(1,n,i)  
  59.         {  
  60.             FOR(0,sum,j)  
  61.             {  
  62.                 for(k=0;k<=num[i]*val[i]&&k+j<=sum;k+=val[i])//也有许多变形，要活学活用  
  63.                 {  
  64.                     c2[j+k]+=c1[j];  
  65.                 }  
  66.             }  
  67.             FOR(0,sum,j)  
  68.             {  
  69.                 c1[j]=c2[j];  
  70.                 c2[j]=0;  
  71.             }  
  72.         }  
  73.         for(i=sum;i>0;--i)//这里操作一般由题目要求什么决定  
  74.         {  
  75.             if(c1[i]!=0)  
  76.             {  
  77.                 break;  
  78.             }  
  79.         }  
  80.         printf("%d %d\n",ans-i,i);  
  81.     }  
  82.     return 0;  
  83. }  

HDU1059 Dividing
首先这题并不算是一个可以用生成函数过题，应该是一个完全背包+二进制转化的题目，但是由于数据较水，进行一些取模运算就可以用生成函数模板运算过了，建议当做模板练手题，然后再用完全背包再过一遍。题意就是问1~6价值的硬币分别有a1~a6个，问能否分为相等的两部分。

[cpp] view
plaincopyprint?

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<algorithm>  
  4. #include<cstring>  
  5. #include<string>  
  6. #include<cmath>  
  7. #include<set>  
  8. #include<vector>  
  9. #include<stack>  
  10. #define mem(a,b) memset(a,b,sizeof(a))  
  11. #define FOR(a,b,i) for(i=a;i<=b;++i)  
  12. #define For(a,b,i) for(i=a;i<b;++i)  
  13. #define N 1000000007  
  14. using namespace std;  
  15. inline void RD(int &ret)  
  16. {  
  17.     char c;  
  18.     do  
  19.     {  
  20.         c=getchar();  
  21.     }  
  22.     while(c<'0'||c>'9');  
  23.     ret=c-'0';  
  24.     while((c=getchar())>='0'&&c<='9')  
  25.     {  
  26.         ret=ret*10+(c-'0');  
  27.     }  
  28. }  
  29. inline void OT(int a)  
  30. {  
  31.     if(a>=10)  
  32.     {  
  33.         OT(a/10);  
  34.     }  
  35.     putchar(a%10+'0');  
  36. }  
  37. int a[7];  
  38. int c1[20001];  
  39. int main()  
  40. {  
  41.     int i,j,k,sum,ans,f,cas=0;  
  42.     while(1)  
  43.     {  
  44.         cas++;  
  45.         f=0;  
  46.         sum=0;  
  47.         FOR(1,6,i)  
  48.         {  
  49.             scanf("%d",&a[i]);  
  50.             if(a[i]==0)  
  51.             {  
  52.                 f++;  
  53.             }  
  54.             a[i]%=10;//这个模10很神奇，缩小了数据量（但估计是数据水了）  
  55.             sum+=a[i]*i;  
  56.         }  
  57.         if(f==6)  
  58.         {  
  59.             break;  
  60.         }  
  61.         ans=sum;  
  62.         printf("Collection #%d:\n",cas);  
  63.         if(ans%2==1)//奇数肯定不能被2整除  
  64.         {  
  65.             printf("Can't be divided.\n");  
  66.         }  
  67.         else  
  68.         {  
  69.             sum/=2;  
  70.             mem(c1,0);  
  71.             c1[0]=1;  
  72.             FOR(1,6,i)  
  73.             {  
  74.                 for(j=sum;j>=0;--j)  
  75.                 {  
  76.                     for(k=1; k<=a[i]&&k*i+j<=sum; k++)//变形  
  77.                     {  
  78.                         c1[j+k*i]|=c1[j];  
  79.                     }  
  80.                 }  
  81.             }  
  82.             if(c1[sum]!=0)  
  83.             {  
  84.                 printf("Can be divided.\n");  
  85.             }  
  86.             else  
  87.             {  
  88.                 printf("Can't be divided.\n");  
  89.             }  
  90.         }  
  91.         printf("\n");  
  92.     }  
  93.     return 0;  
  94. }  


HDU1398 Square Coins

这也算是一道生成函数的好题，一种与完全平方数的结合。题意很简单，给你一个n，问你n可以由完全平方数组成的方案数。

Y=(1+x+x^2+...+x^n)*(1+x^2+x^4+...)*...

[cpp] view
plaincopyprint?

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<algorithm>  
  4. #include<cstring>  
  5. #include<string>  
  6. #include<cmath>  
  7. #include<set>  
  8. #include<vector>  
  9. #include<stack>  
  10. #define mem(a,b) memset(a,b,sizeof(a))  
  11. #define FOR(a,b,i) for(i=a;i<=b;++i)  
  12. #define For(a,b,i) for(i=a;i<b;++i)  
  13. #define N 1000000007  
  14. using namespace std;  
  15. inline void RD(int &ret)  
  16. {  
  17.     char c;  
  18.     do  
  19.     {  
  20.         c=getchar();  
  21.     }  
  22.     while(c<'0'||c>'9');  
  23.     ret=c-'0';  
  24.     while((c=getchar())>='0'&&c<='9')  
  25.     {  
  26.         ret=ret*10+(c-'0');  
  27.     }  
  28. }  
  29. inline void OT(int a)  
  30. {  
  31.     if(a>=10)  
  32.     {  
  33.         OT(a/10);  
  34.     }  
  35.     putchar(a%10+'0');  
  36. }  
  37. int c1[301],c2[301];  
  38. int main()  
  39. {  
  40.     int n,i,j,k;  
  41.     while(1)  
  42.     {  
  43.         RD(n);  
  44.         if(n==0)  
  45.         {  
  46.             break;  
  47.         }  
  48.         FOR(0,n,i)  
  49.         {  
  50.             c1[i]=1;  
  51.             c2[i]=0;  
  52.         }  
  53.         for(i=2;i*i<=n;++i)//这就是为完全平方数做的准备  
  54.         {  
  55.             FOR(0,n,j)  
  56.             {  
  57.                 for(k=0;k+j<=n;k+=i*i)//这里的处理，要根据情况不同变换  
  58.                 {  
  59.                     c2[k+j]+=c1[j];  
  60.                 }  
  61.             }  
  62.             FOR(0,n,j)  
  63.             {  
  64.                 c1[j]=c2[j];  
  65.                 c2[j]=0;  
  66.             }  
  67.         }  
  68.         printf("%d\n",c1[n]);  
  69.     }  
  70.     return 0;  
  71. }  


HDU1028也是一道生成函数可以解决的题目，但我用五角数公式过了，就不深入了，可以作为练手。

POJ3734 Blocks

不得不说poj的这道生成函数相比上面的模板套用，模板变形题要有深度。这题可以用矩阵乘做，但今天是生成函数专题，就不像昨天那样了。这题题意是可以用红蓝绿黄四种

给模块涂色，且要求红色与绿色的模块数必须为偶数。生成函数本来就可以解决组合数学的问题，所以这题再合适不过了。

根据生成函数公式我们可以得到这样一个式子：Y=[(1+x+x^2/2!+x^3/3!+x^4/4!...)^2]*[(1+x^2/2!+x^4/4!+...)^2]

这个式子里乘号前是蓝色和黄色的方案，乘号后是红色与绿色的方案。由于是求组合数，颜色相同时前后放置为同一种情况，所以需要除以排列数。

推导过程：

Y==>(由泰勒展式)1/4*e^2x*(e^x+e^(-x))^2==>1/4*(e^4x+2e^2x+1)==>(逆推导)1/4*sigma(4^i+2*2^i)*x^i

所以系数就是1/4(4^n+2*2^n)==>(4^(n-1)+2^(n-1))，这样就是可以直接用快速幂取模得到。。。

[cpp] view
plaincopyprint?

  1. #include<iostream>  
  2. #include<cstdio>  
  3. #include<algorithm>  
  4. #include<cstring>  
  5. #include<string>  
  6. #include<cmath>  
  7. #include<set>  
  8. #include<vector>  
  9. #include<stack>  
  10. #define mem(a,b) memset(a,b,sizeof(a))  
  11. #define FOR(a,b,i) for(i=a;i<=b;++i)  
  12. #define For(a,b,i) for(i=a;i<b;++i)  
  13. #define N 10007  
  14. using namespace std;  
  15. inline void RD(int &ret)  
  16. {  
  17.     char c;  
  18.     do  
  19.     {  
  20.         c=getchar();  
  21.     }  
  22.     while(c<'0'||c>'9');  
  23.     ret=c-'0';  
  24.     while((c=getchar())>='0'&&c<='9')  
  25.     {  
  26.         ret=ret*10+(c-'0');  
  27.     }  
  28. }  
  29. inline void OT(int a)  
  30. {  
  31.     if(a>=10)  
  32.     {  
  33.         OT(a/10);  
  34.     }  
  35.     putchar(a%10+'0');  
  36. }  
  37. __int64 p(__int64 x,__int64 y)//快速幂取模  
  38. {  
  39.     __int64 res=1;  
  40.     while(y>0)  
  41.     {  
  42.         if(y%2==1)  
  43.         {  
  44.             res=(res*x)%N;  
  45.         }  
  46.         x=(x*x)%N;  
  47.         y/=2;  
  48.     }  
  49.     return res%N;  
  50. }  
  51. int main()  
  52. {  
  53.     int t,n;  
  54.     __int64 sum;  
  55.     RD(t);  
  56.     while(t--)  
  57.     {  
  58.         RD(n);  
  59.         sum=(p(4,n-1)+p(2,n-1))%N;  
  60.         printf("%I64d\n",sum);  
  61.     }  
  62.     return 0;  
  63. }  

POJ2084 Game of Connections

卡特兰数，由于通项公式可由生成函数得到，所以也发一道。。。

令h(0)=1,h(1)=1，catalan数满足递推式[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);
递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,...)
递推关系的另类解为：
h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,...)

这题是道高精度，直接java搞了，没难度。

[java] view
plaincopyprint?

  1. import java.io.*;    
  2. import java.math.*;    
  3. import java.util.*;    
  4. import java.text.*;    
  5. public class Main    
  6. {    
  7.     public static void main(String[] args)    
  8.     {    
  9.         Scanner cin=new Scanner(System.in);    
  10.         BigInteger sum,ans;    
  11.         int n,i;    
  12.         while(true)    
  13.         {    
  14.             n=cin.nextInt();   
  15.             if(n==-1)  
  16.             {  
  17.                 break;  
  18.             }  
  19.             sum=BigInteger.ONE;  
  20.             ans=BigInteger.ONE;  
  21.             for(i=1;i<=n;++i)  
  22.             {  
  23.                 sum=sum.multiply(BigInteger.valueOf(i));  
  24.                 ans=ans.multiply(BigInteger.valueOf(2*n-i+1));  
  25.             }  
  26.             ans=ans.divide(sum);  
  27.             ans=ans.divide(BigInteger.valueOf(n+1));  
  28.             System.out.println(ans);    
  29.         }    
  30.     }    
  31. }   
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞