记录编号	49396	评测结果	AAAAA
题目名称	三只小猪	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.576 s
提交时间	2012-11-07 19:49:13	内存使用	52.81 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct bint
{
	int len,num[5000];
}bnum0,bnum1,f[51][51];

bint bchange(int num)
{
	bint a={0};
	if (!num)
	{
		a.len=1;
		return(a);
	}
	while (num)
	{
		a.num[a.len++]=num%10;
		num/=10;
	}
	return(a);
}

bint bplus(bint a,bint b)
{
	int i,mlen,jin;
	mlen=a.len;
	if (mlen<b.len)
		mlen=b.len;
	for (i=0;i<mlen;i++)
		b.num[i]+=a.num[i];
	jin=0;
	for (i=0;i<mlen;i++)
	{
		b.num[i]+=jin;
		jin=b.num[i]/10;
		b.num[i]%=10;
	}
	if (jin)
	{
		b.num[mlen]=jin;
		b.len=mlen+1;
	}
	else
		b.len=mlen;
	return(b);
}

bint bmul(bint a,bint b)
{
	bint c={0};
	int i,j,jin;
	c.len=a.len+b.len-1;
	for (i=0;i<a.len;i++)
		for (j=0;j<b.len;j++)
			c.num[i+j]+=a.num[i]*b.num[j];
	jin=0;
	for (i=0;i<=c.len;i++)
	{
		c.num[i]+=jin;
		jin=c.num[i]/10;
		c.num[i]%=10;
	}
	if (c.num[c.len])
	{
		c.len++;
	}
	return(c);
}

void bprint(bint a)
{
	int i;
	for (i=a.len-1;i>=0;i--)
		cout<<a.num[i];
}

int main(void)
{
	freopen("piggy.in","r",stdin);
	freopen("piggy.out","w",stdout);
	int times,T,n,m;
	bnum0=bchange(0);
	bnum1=bchange(1);
	for (n=0;n<=50;n++)
		for (m=0;m<=50;m++)
			f[n][m]=bnum0;
	for (n=1;n<=50;n++)
	{
		f[n][1]=bnum1;
		f[n][n]=bnum1;
		for (m=1;m<n;m++)
			f[n][m]=bplus(bmul(f[n-1][m],bchange(m)),f[n-1][m-1]);
	}
	cin>>T;
	for (times=1;times<=T;times++)
	{
		cin>>n>>m;
		bprint(f[n][m]);
		cout<<endl;
	}
	return(0);
}