poj 2506 Tiling(大數+規律)

poj 2506 Tiling(大數+規律)

poj2506Tiling
此題規律：A[0]=1;A[1]=1;A[2]=3;……A[n]=A[n-1]+2*A[n-2];用大數來寫，AC代碼：

#include
#include
#define MAX 300
int num[MAX][MAX];
int main()
{
    int n;
    while(scanf(%d,&n)!=EOF)
    {
        memset(num,0,sizeof(num));
        num[0][0]=1;
        num[1][0]=1;
        for(int i=2;i<=MAX;i++)
        {
            int t=0,k;
            for(int j=0;j<=MAX;j++)
            {
                k=2*num[i-2][j]+num[i-1][j]+t;
                num[i][j]=k%10;
                t=k/10;
            }       
        }
        int i;
        for(i=MAX-1;num[n][i]==0;i--);
        printf(%d,num[n][i]);
        while(i)
            printf(%d,num[n][--i]);
        printf(
);
    }
    return 0;
}