记录编号	126282	评测结果	AAAAA
题目名称	三只小猪	最终得分	100
用户昵称	chs	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2014-10-11 21:33:37	内存使用	0.53 MiB

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int maxn=21;
const int base=10000;
class bign
{
	public:
		int len;
		int num[maxn];
};
void binit(bign &a,int x)
{
	a.len=0;
	while(x>0)
	{
		int temp=x%base;
		a.num[a.len++]=temp;
		x/=base;
	}
}
void bprint(bign a)
{
	if(a.len==0)
	{
		cout<<0<<endl;
		return ;
	}
	cout<<a.num[a.len-1];
	for(int i=a.len-2;i>=0;i--) printf("%04d",a.num[i]);
	cout<<endl;
}
bign bplus(bign a,bign b)
{
	a.len=max(a.len,b.len);
	for(int i=0;i<a.len;i++)
	{
		a.num[i]+=b.num[i];
	}
	for(int i=0;i<a.len-1;i++)
	{
		if(a.num[i]>=base)
		{
			a.num[i+1]+=a.num[i]/base;
			a.num[i]%=base;
		}
	}
	if(a.num[a.len-1]>=base)
	{
		a.num[a.len]+=a.num[a.len-1]/base;
		a.num[a.len-1]%=base;
		a.len++;
	}
	return a;
}
bign bmul(bign a,bign b)
{
	bign c={0};
	c.len=a.len+b.len-1;
	for(int i=0;i<a.len;i++)
		for(int j=0;j<b.len;j++)
			c.num[i+j]=a.num[i]*b.num[j];
	for(int i=0;i<c.len-1;i++)
	{
		if(c.num[i]>=base)
		{
			c.num[i+1]+=c.num[i]/base;
			c.num[i]%=base;
		}
	}
	if(c.num[c.len-1]>=base)
	{
		c.num[c.len]+=c.num[c.len-1]/base;
		c.num[c.len-1]%=base;
		c.len++;
	}
	return c;
}
//=========== 主程序 ===========//
const int M=50;
bign F[M+1][M+1];
void init()
{
	int i,j;
	for(i=0;i<=M;i++)
	{
		for(j=0;j<=M;j++)
		{
			if(i>=1&&i==j) binit(F[i][j],1);
			else binit(F[i][j],0);
		}
	}
	int p,k;
	for(p=1;p<=M;p++)
	{
		for(k=1;k<p;k++)
		{
			bign temp;
			binit(temp,k);
			F[p][k]=bplus(bmul(temp,F[p-1][k]),F[p-1][k-1]);
		}
	}
}
void print()
{
	int T;
	int n,m;
	cin>>T;
	for(int i=1;i<=T;i++)
	{
		cin>>n>>m;
		bprint(F[n][m]);
	}
}
int main()
{
	freopen("piggy.in","r",stdin);
	freopen("piggy.out","w",stdout);
	init();
	print();
	return 0;
}