binomial

#include <inttypes.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAXLEN 251
#define BASE 1e9

typedef uint32_t* bInt;

bInt _binit( uint16_t len) {
    bInt num = (bInt)calloc( MAXLEN, sizeof(uint32_t));
    num[0] = 1;

    return num;
}

bInt binit() {
    return _binit(MAXLEN);
}

char* bprint( const bInt num) {
    uint16_t i = num[0];

    char* buff = (char*)calloc( ( i ? 9 * i : 1) + 1, sizeof(char));
    char  aux[10] = {0};
    buff[0] = '\0';

    sprintf( aux, "%d", ( i ? num[i--] : 0));
    strcat( buff, aux);

    while( i > 0) {
        sprintf( aux, "%09d", num[i--]);
        strcat( buff, aux);
    }

    return buff;
}

bInt copy( const bInt num) {
    bInt cnum = binit();
    memcpy( cnum, num, sizeof(uint32_t) * MAXLEN);

    return cnum;
}

bInt add( const bInt a, const bInt b) {
    bInt c = copy( a[0] >= b[0] ? a : b);
    const bInt d =  a[0] < b[0] ? a : b;
    uint16_t i = 1;

    uint32_t t = 0;
    while( i <= d[0] || t) {
        c[i] += t + d[i];
        if( t = (c[i] >= BASE))
            c[i] -= BASE;

        ++i;
    }

    if( c[c[0] + 1])c[0]++;
    return c;
}

bInt binomial( const uint16_t n, const uint16_t k) {
    bInt* a = (bInt*)calloc( n + 1, sizeof(bInt));
    bInt* b = (bInt*)calloc( n + 1, sizeof(bInt));

    for( uint16_t i = 0; i <= n; ++i)
        a[i] = binit(), b[i] = binit();
    a[1][1] = 1;

    for( uint16_t line = 1; line <= n; ++line) {
        for( uint16_t i = 1; i <= line; ++i) {
            free( b[i]);
            b[i] = add( a[i - 1], a[i]);
        }

        bInt* aux = a; a = b; b = aux;
    }

    bInt res = copy( a[k]);

    for( uint16_t i = 0; i <= n; ++i)
        free( a[i]), free( b[i]);

    return res;
}

int main( int argc, char* argv[]) {
    uint16_t n, k;
    scanf( "%" SCNu16 " %" SCNu16, &n, &k);

    bInt bc = binomial( n + 1, k + 1);
    printf( "%s\n", bprint( bc));
    free( bc);

    return 0;
}