1003.cpp

HDOJ 5月2日 “老菜鸟杯”程序大赛标准程序+解题报告

#include<stdio.h>
#define MAXN 1001
__int64 YH[MAXN][MAXN];
__int64 ans[MAXN];
int main()
{
// 	freopen("in.in","r",stdin);
// 	freopen("out.out","w",stdout);
	int i,j,n,mod;
	while(scanf("%d%d",&n,&mod)==2)
	{
		for(i=0;i<n;i++) {
			for(j=0;j<=i;j++) {
				if(j==0 || i==j)
					YH[i][j] = 1;
				else
					YH[i][j] = (YH[i-1][j] + YH[i-1][j-1]) % mod;
			}
		}
		ans[0] = ans[1] = 1;
		for(i=2;i<=n;i++)
		{
			ans[i] = 0;
			for(j=0;j<i/2;j++)
				ans[i] = (ans[i] + ((YH[i-1][j] * ans[j]) % mod) * ans[i-1-j]) % mod;
			if(i&1)
				ans[i] = (ans[i] + ((YH[i-2][(i-1)/2] * ans[(i-1)/2]) % mod) * ans[(i-1)/2]) % mod;
		}
		printf("%d\n",ans[n]);
	}
	return 0;
}