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

Output

Sample Input

2
8
12
100
200

Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

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

递推公式不难，Ai=Ai-1+2*Ai-2，很容易就想清楚了

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
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"<<endl;continue;}
        int bj=0;
        memset(a,0,sizeof a);
        a[1][0]=1;a[2][0]=3;
        x=0;y=0;
        for(i=3;i<=251;i++)
           work(i);
        for(i=z-1;i>=0;i--)
        {
            if(bj==0&&a[n][i]==0)
            continue;
            if(a[n][i]!=0)
                bj=1;
            cout<<a[n][i];
        }
        cout<<endl;
    }
    return 0;
}