生成函数练习小结

系统 1961 0

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

 

    #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 

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

        {

            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])//也有许多变形,要活学活用

                {

                    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
首先这题并不算是一个可以用生成函数过题,应该是一个完全背包+二进制转化的题目,但是由于数据较水,进行一些取模运算就可以用生成函数模板运算过了,建议当做模板练手题,然后再用完全背包再过一遍。题意就是问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很神奇,缩小了数据量(但估计是数据水了)

            sum+=a[i]*i;

        }

        if(f==6)

        {

            break;

        }

        ans=sum;

        printf("Collection #%d:\n",cas);

        if(ans%2==1)//奇数肯定不能被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

 

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

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)//这就是为完全平方数做的准备

        {

            FOR(0,n,j)

            {

                for(k=0;k+j<=n;k+=i*i)//这里的处理,要根据情况不同变换

                {

                    c2[k+j]+=c1[j];

                }

            }

            FOR(0,n,j)

            {

                c1[j]=c2[j];

                c2[j]=0;

            }

        }

        printf("%d\n",c1[n]);

    }

    return 0;

}
  


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)),这样就是可以直接用快速幂取模得到。。。

 

    #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

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

令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搞了,没难度。

 

    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);  

        }  

    }  

} 
  



 

 

生成函数练习小结


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论