Tiling

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7437		Accepted: 3635

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

2812100200

Sample Output

317127318451004001521529343311354702511071292029505993517027974728227441735014801995855195223534251

特别注意输入0。输出1！。！！

。！

！

递推公式不难，Ai=Ai-1+2*Ai-2。非常easy就想清楚了

AC代码例如以下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int a[300][3005],b[3005];int x,y,z;void work(int c){    int i;    memset(b,0,sizeof b);    for(i=0;i<=x;i++)    {        b[i]+=(a[c-2][i]*2);        if(b[i]>10)        {            b[i]=b[i]%10;            x++;            b[i+1]=1;        }    }    z=x+2;    for(i=0;i<=z+2;i++)    {        a[c][i]+=a[c-1][i]+b[i];        if(a[c][i]>=10&&i==z+1)            z++;        if(a[c][i]>=10)        {            a[c][i]=a[c][i]%10;            a[c][i+1]=1;        }    }    x=y;y=z;}int main(){    int n;    int i;    while(cin>>n)    {        if(n==0)        {cout<<"1"<
          
           =0;i--) { if(bj==0&&a[n][i]==0) continue; if(a[n][i]!=0) bj=1; cout<