LATGACH - Lát gạch

Tác giả: happyboy99x

Ngôn ngữ: C++

#include <cstdio>
#include <algorithm>
using namespace std;

#define L_MAX 1000 //length max
#define RADIX 1000000000
#define N_MAX 100 + 2

#define REP(i, n) for( int i = 0, _n = (n); i < _n ; ++i )
#define REPD(i, n) for( int i = (n)-1; i >= 0; --i )
#define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i )

int f[N_MAX][L_MAX];
int l[N_MAX];
int countNum;

//----------------------------PROTOTYPE-------------------------------
void init();
void calc(int, int);
void plus(int *, int *, int *, int, int, int & );
void print( int *, int l );
//--------------------------------------------------------------------

void init() {
   f[0][0] = 0; l[0] = 1;
   f[1][0] = 1; l[1] = 1;
   countNum = 2;
}

void calc( int a, int b ) {
    countNum = b + 1;
    FOR(i, a, b) plus( f[i-1], f[i-2], f[i], l[i-1], l[i-2], l[i] );
}

void print( int a[], int l ) {
    printf( "%d", a[l-1] );
    REPD(i, l-1) printf( "%09d", a[i] );
}

void plus( int a[], int b[], int c[], int la, int lb, int &lc ) {
    int carry = 0;
    lc = max(la, lb);
    REP(i, lc) {
        c[i] = a[i] + b[i] + carry;
        if ( c[i] >= RADIX ) {
            carry = 1;
            c[i] -= RADIX;
        } else carry = 0;
    }
    if (carry) c[lc++] = 1;
}

int main() {
    init();
	int tc, n; scanf("%d",&tc);
    while ( tc-- && scanf( "%d", &n) == 1 ) {
        if ( n+1 >= countNum ) calc( countNum, n+1 );
        print( f[n+1], l[n+1] );
        printf( "\n" );
    }
	return 0;
}

Download