a208231.cpp

#include <stdio.h>
#include <algorithm>
#include "gmp.h"

const int M = 3000;

mpz_t fact[M+1];
mpz_t binomial[M+1][M+1];
mpz_t b[M+1][M+1];
mpz_t a[M+1];

void initialize()  {
    mpz_t prod;
    mpz_init(prod);
    mpz_set_ui(prod, 1);
    mpz_init(fact[0]);
    mpz_set_ui(fact[0], 1);
    for (int i = 1; i <= M; i ++) {
        mpz_mul_ui(prod, prod, i);
        mpz_init(fact[i]);
        mpz_set(fact[i], prod);
    }
    mpz_clear(prod);

    mpz_init(binomial[0][0]);
    mpz_set_ui(binomial[0][0], 1);
    for (int n = 1; n <= M; n ++) {
        for (int k = 0; k <= n; k ++) {
            mpz_init(binomial[n][k]);
            if (k != 0) mpz_add(binomial[n][k], binomial[n][k], binomial[n-1][k-1]);
            if (k != n) mpz_add(binomial[n][k], binomial[n][k], binomial[n-1][k]);
        }
    }
    for (int n = 0; n <= M; n ++) {
        for (int m = 0; m <= M; m ++) {
            mpz_init(b[n][m]);
            mpz_set_ui(b[n][m], -1);
        }
    }
}

void calc_b(int n, int m) {
    if (mpz_cmp_ui(b[n][m], -1) != 0) {
        return;
    }
    if (n == 0) {
        mpz_set_ui(b[n][m], m);
        return;
    }
    mpz_t t;
    mpz_init(t);
    mpz_set_ui(b[n][m], 0);
    for (int j = 1; j <= n; j ++) {
        calc_b(n - j, std::min(m, j));
        mpz_set(t, fact[j - 1]);
        mpz_mul(t, t, b[n - j][std::min(m, j)]);
        mpz_mul(t, t, binomial[n - 1][j - 1]);
        mpz_add(b[n][m], b[n][m], t);
    }
    mpz_clear(t);
}

void calc_a(int n) {
    mpz_t power;
    mpz_init(power);
    mpz_set_ui(power, 1);
    mpz_t t;
    mpz_init(t);
    mpz_init(a[n]);
    mpz_set_ui(a[n], 0);
    for (int j = 0; j < n; j ++) {
        calc_b(n - j, n - j);
        mpz_set(t, b[n - j][n - j]);
        mpz_mul(t, t, power);
        mpz_mul(t, t, binomial[n - 1][n - j - 1]);
        mpz_add(a[n], a[n], t);
        mpz_mul_ui(power, power, n);
    }
    mpz_clear(t);

}

int main(int argc, char *argv[])
{
    initialize();
    for (int n = 0; n <= M; n ++) {
        calc_a(n);
        printf("%d\t", n);
        mpz_out_str(stdout, 10, a[n]);
        puts("");
        fflush(stdout);
    }
    return 0;
}