Tiling

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

Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

 1 #include<stdio.h>
 2 #include<string.h>
 3 int ans[250][500];
 4 int main()
 5 {
 6     int n,i,j;
 7     while(~scanf("%d",&n))
 8     {
 9         memset(ans,0,sizeof(ans));
10         ans[0][0] = 1;
11         ans[1][0] = 1;
12         ans[2][0] = 3;
13         if(n <= 2)
14             printf("%d
",ans[n][0]);
15         else
16         {
17             int cnt = 1,s,beyond;
18             for(i = 3; i <= n; i++)
19             {
20                 beyond = 0;
21                 for(j = 0; j < cnt; j++)
22                 {
23                     s = ans[i-2][j]*2 + ans[i-1][j] + beyond;
24                     ans[i][j] = s%10;
25                     beyond = s/10;
26                 }
27                 if(beyond)
28                 {
29                     ans[i][cnt] = beyond;
30                     cnt++;
31                 }
32             }
33             for(i = cnt-1; i >= 0; i--)
34                 printf("%d",ans[n][i]);
35             printf("
");
36         }
37     }
38     return 0;
39 }

View Code