hdu-1133,1131 依然Catalan数

俩题惊人的相似嗄 唉 有个打算把ACM Step的题挨个总结一下、、、、、稍后有时间了 写写吧

加油！吖飒~~~~~

http://acm.hdu.edu.cn/showproblem.php?pid=1133

本题依然是Catalan数。稍加变形而已。公式的推导结果为：C[i][j]=(i+j)*(i+1-j)/j/(i+2-j)*C[i][j-1];

http://acm.hdu.edu.cn/showproblem.php?pid=1131

还是Catalan数，公式：C[i][j]=(4n-2)/(n+1)*C[i][j-1]

1131Conut the tree的代码及解释：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int num[101][400];
int len[101];
void Catalan()
{
    int i,j;
    num[0][0]=1;
    num[1][0]=1;
    len[0]=1;
    int flag;
    for(i=2;i<101;i++)
    {
        //乘4n-2
        int k=4*i-2;
        flag=0;
        for(j=0;j<=len[i-1];j++)
        {
            int z=flag+num[i-1][j]*k;
            num[i][j]=z%10;
            flag=z/10;
        }
        while(flag)
        {
            num[i][j++]=flag%10;
            flag/=10;
        }
        len[i]=j;flag=0;
        //除n+1
        while(j>=0)
        {
            int w=num[i][j]+flag*10;
            num[i][j]=w/(i+1);
            flag=w%(i+1);
            j--;
        }
    }
}
int fun()//在求的的Catalan数的基础上乘m的阶乘
{
	int i,k,m;
	for(m=1;m<101;m++)
	{			
		for(i=1;i<=m;i++)
		{
			int flag=0;
			for(k=0;k<len[m];k++)
			{
				int w=i*num[m][k]+flag;
				num[m][k]=w%10;
				flag=w/10;
			}
			while(flag)
			{
				num[m][k++]=flag%10;
				flag/=10;
			}
			len[m]=k;
		}
	}
	return 0;
}
int main()
{
    Catalan();
	fun();
    int m;
	len[1]=1;
	int cnt=1;
    while(cin>>m&&m)
    {
		int i=len[m]-1;
		while(i>=0)
			cout<<num[m][i--];
		cout<<endl;		
    }
    return 0;
}

1133Buy the ticket的代码及解释：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int C[101][101][400];
int len[101][101];
int Catalan()
{
	memset(len,0,sizeof(len));
	memset(C,0,sizeof(C));
    int i,j,k;
    for(i=1;i<=100;i++)
    {
        C[i][0][0]=1;
		len[i][0]=1;
		//乘(i+j)*(i+1-j)
        for(j=1;j<=i;j++)
        {
            int flag=0;
            for(k=0;k<len[i][j-1];k++)
            {
                int w=(i+j)*(i+1-j)*C[i][j-1][k]+flag;
                C[i][j][k]=w%10;
                flag=w/10;
            }
            while(flag)
            {
                C[i][j][k++]=flag%10;
                flag/=10;
            }
            len[i][j]=k;
			//除j*(i+2-j)
			int z=j*(i+2-j);
            while(k>=0)
            {
                int y=C[i][j][k]+flag*10;
                C[i][j][k]=y/z;
                flag=y%z;
                k--;
            }
        }
    }
    return 0;
}
int fun()//在求的的Catalan数的基础上乘m的阶乘再乘n的阶乘
{
	int i,k,m,n;
	for(m=1;m<101;m++)
	{
///////////当n=0的时候
		for(i=1;i<=m;i++)
		{
			int flag=0;
			for(k=0;k<len[m][0];k++)
			{
				int w=i*C[m][0][k]+flag;
				C[m][0][k]=w%10;
				flag=w/10;
			}
			while(flag)
			{
				C[m][0][k++]=flag%10;
				flag/=10;
			}
			len[m][0]=k;
		}
		for(n=1;n<=m;n++)
		{			
			for(i=1;i<=m;i++)
			{
				int flag=0;
				for(k=0;k<len[m][n];k++)
				{
					int w=i*C[m][n][k]+flag;
					C[m][n][k]=w%10;
					flag=w/10;
				}
				while(flag)
				{
					C[m][n][k++]=flag%10;
					flag/=10;
				}
				len[m][n]=k;
			}

			for(i=1;i<=n;i++)
			{
				int flag=0;
				for(k=0;k<len[m][n];k++)
				{
					int w=i*C[m][n][k]+flag;
					C[m][n][k]=w%10;
					flag=w/10;
				}
				while(flag)
				{
					C[m][n][k++]=flag%10;
					flag/=10;
				}
				len[m][n]=k;
			}
		}
	}
	return 0;
}
int main()
{
    Catalan();
	fun();
    int m,n;
	int cnt=1;
    while(cin>>m>>n&&(m+n)!=0)
    {
		printf("Test #%d:\n",cnt++);  
		if(m<n) cout<<"0"<<endl;
		else
		{
			int i=len[m][n]-1;
			while(i>=0)
				cout<<C[m][n][i--];
			cout<<endl;
		}
		
    }
    return 0;
}