ACM 10359 - Tiling

#include <stdio.h>
#define MAXLEN 251
#define LEN 76
struct til
{
    int num[100];       
};
struct til t[MAXLEN];
struct til s;

void mult2s()
{
     int i, j;
     for (i = 0; i < LEN; i ++)
         s.num[i] *= 2;
     for (i = 0; i < LEN; i ++)
         if (s.num[i] >= 10)
            s.num[i + 1] ++, s.num[i] %= 10;
}

void add(int n)
{
    int i;
    for (i = 0; i < LEN; i ++)
    {
        t[n].num[i] += s.num[i];
        if (t[n].num[i] >= 10)
           t[n].num[i + 1] ++, t[n].num[i] %= 10;
    }
    
    for (i = 0; i < LEN; i ++)
    {
        t[n].num[i] += t[n - 1].num[i];
        if (t[n].num[i] >= 10)
           t[n].num[i + 1] ++, t[n].num[i] %= 10;
    }
}

void creat()
{
    int i, j; 
    t[0].num[0] = 1, t[1].num[0] = 1, t[2].num[0] = 3;
    for (i = 3; i < MAXLEN; i ++)
    {
        for (j = 0; j < LEN; j ++)
            s.num[j] = t[i - 2].num[j];
        mult2s();
        add(i);
    } 
}


int main()
{
    int n, i, j;
    creat();
    while (scanf("%d", &n) == 1)
    {
        for (i = LEN - 1; i >= 0; i --)
            if (t[n].num[i] > 0) break;
        for (j = i; j >= 0; j --)
            printf("%d", t[n].num[j]);
        printf("\n");         
    }  
    return 0;
}

回目錄
回首頁