记录编号	49069	评测结果	AAAAA
题目名称	三只小猪	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-11-07 12:12:30	内存使用	8.33 MiB

#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=105;
const int MAXL=200;
int bign=0,bigm=0,T;
int nn[MAXN],mm[MAXN];
class hugeint{public:int len,num[MAXL];
void clear(){memset(num,0,sizeof(num));len=0;}};
hugeint ichi,zero,ans;
hugeint F[MAXN][MAXN];
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
inline void init()
{
	scanf("%d\n",&T);
	for(int i=1;i<=T;i++)
	{
		scanf("%d %d\n",&nn[i],&mm[i]);
		if(nn[i]>bign) bign=nn[i];
		if(mm[i]>bigm) bigm=mm[i];
	}
}

inline hugeint times(hugeint a,hugeint b)
{
	hugeint res;res.clear();
	res.len=a.len+b.len-1;
	for(int i=1;i<=a.len;i++)
		for(int j=1;j<=b.len;j++)
			res.num[i+j-1]+=(a.num[i]*b.num[j]);
	for(int i=1;i<=res.len;i++)
	{
		res.num[i+1]+=res.num[i]/10;
		res.num[i]%=10;
	}	if(res.num[res.len+1]) res.len++; 
	return res;
}

inline hugeint plusadd(hugeint a,hugeint b)
{
	hugeint res;res.clear();
	res.len=Max(a.len,b.len);
	for(int i=1;i<=res.len;i++)
	{
		res.num[i]+=(a.num[i]+b.num[i]);
		res.num[i+1]+=res.num[i]/10;
		res.num[i]%=10;
	}if(res.num[res.len+1]) res.len++;
	return res;
}

inline hugeint trans(int k)
{
	hugeint res;res.clear();
	while(k)
	{
		res.num[++res.len]=k%10; k/=10;
	}return res;
}

inline void print(hugeint& res)
{
	if(res.len==0) {printf("0\n");return;}
	for(int i=res.len;i>=1;i--)
		printf("%d",res.num[i]);printf("\n");
}

inline void makestr()
{
	ichi.clear();ichi.len=1;ichi.num[1]=1;
	zero.clear();zero.len=1;zero.num[1]=0;
	F[0][0]=ichi;
	hugeint tres,ttime,tplus;
	for(int i=1;i<=bigm;i++) F[0][i]=zero;
	for(int i=1;i<=bign;i++) F[i][0]=zero;
	for(int i=1;i<=bign;i++)
		for(int j=1;j<=Min(i,bigm);j++)
		{
			tres=trans(j);
			ttime=times(tres,F[i-1][j]);
			tplus=plusadd(ttime,F[i-1][j-1]);
			F[i][j]=tplus;
		//	F[i][j]=plusadd(times(trans(j),F[i-1][j]),F[i-1][j-1]);
			//j*F[i-1][j]+F[i-1][j-1];
		}
}

int main()
{
	freopen("piggy.in","r",stdin);
	freopen("piggy.out","w",stdout);
	init(); makestr();
	for(int i=1;i<=T;i++)
		print(F[nn[i]][mm[i]]);
	return 0;
}