poj 2506 Tiling 《大数加法+递推》

Tiling
Time Limit: 1000MS  Memory Limit: 65536K 
Total Submissions: 8689  Accepted: 4183 

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles? 
Here is a sample tiling of a 2x17 rectangle. 

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.
Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle. 

Sample Input

2
8
12
100
200
Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

Source

The UofA Local 2000.10.14

神题。。。n=0时，输出1。。。。。。。。。。

代码：

#include<cstdio>
#include<cstring>
int s[50],n;
int ge[310][200],shu[310];
void suan(int xx)
{
	int ii=xx;
	shu[ii]=shu[ii-1];
	for (int i=0;i<shu[ii];i++)
	{
		ge[ii][i]=ge[ii][i]+ge[ii-1][i]+ge[ii-2][i]*2;
		if (ge[ii][shu[ii]-1]>9)
		shu[ii]++;
		if (ge[ii][i]>9)
		{
			ge[ii][i+1]=ge[ii][i]/10;
			ge[ii][i]=ge[ii][i]%10;
		}
	}
}
int main()
{
	s[0]=1;s[1]=1;s[2]=3;
	for (int i=3;i<31;i++)
	{
		s[i]=s[i-1]+2*s[i-2];
	}
	memset(ge,0,sizeof(ge));
	ge[29][0]=1;ge[29][1]=4;ge[29][2]=9;ge[29][3]=3;ge[29][4]=1;ge[29][5]=9;ge[29][6]=7;ge[29][7]=5;ge[29][8]=3;
	ge[30][0]=3;ge[30][1]=8;ge[30][2]=8;ge[30][3]=7;ge[30][4]=2;ge[30][5]=8;ge[30][6]=5;ge[30][7]=1;ge[30][8]=7;
	shu[29]=9;shu[30]=9;
	for (int i=31;i<305;i++)
    {
	    suan(i);
	}	
	while (~scanf("%d",&n))
	{
		if (n<31)
		{
			printf("%d\n",s[n]);
			continue;
		}
		for (int i=shu[n]-1;i>=0;i--)
		printf("%d",ge[n][i]);
		printf("\n");
	}
	return 0;
}