106 lines
1.9 KiB
C
106 lines
1.9 KiB
C
#include <gmp.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
#define MAX_BRANCH 4
|
|
#define MAX_N 500
|
|
|
|
mpz_t bcache[MAX_N + 1];
|
|
mpz_t ucache[MAX_N + 1];
|
|
mpz_t *rcache[MAX_N + 1][MAX_BRANCH + 1];
|
|
|
|
mpz_t tmp1, tmp2;
|
|
void choose(mpz_t r, mpz_t m, int k)
|
|
{
|
|
int i;
|
|
mpz_set(r, m);
|
|
|
|
mpz_add_ui(tmp1, m, 1);
|
|
for (i = 1; i < k; ) {
|
|
mpz_mul(r, r, tmp1);
|
|
mpz_divexact_ui(r, r, ++i);
|
|
|
|
if (i >= k) break;
|
|
mpz_add_ui(tmp1, tmp1, 1);
|
|
}
|
|
}
|
|
|
|
mpz_t rtmp1, rtmp2;
|
|
void calc_rooted(mpz_t res, int n, int b, int r)
|
|
{
|
|
mpz_set_ui(res, 0);
|
|
|
|
if (n == 1 && b == 0 && r == 0) {
|
|
mpz_set_ui(res, 1);
|
|
return;
|
|
} else if (n <= b || n <= r || n == 1 || b == 0 || r == 0)
|
|
return;
|
|
|
|
int b1, r1;
|
|
for (b1 = 1; b1 <= b && r * b1 < n; b1++) {
|
|
choose(rtmp1, bcache[r], b1);
|
|
mpz_set_ui(rtmp2, 0);
|
|
for (r1 = 0; r1 < r && r1 + r * b1 < n; r1++)
|
|
mpz_add(rtmp2, rtmp2, rcache[n - r * b1][b - b1][r1]);
|
|
|
|
mpz_addmul(res, rtmp1, rtmp2);
|
|
}
|
|
}
|
|
|
|
void calc_first_branch(int n)
|
|
{
|
|
int b, r;
|
|
mpz_init_set_ui(bcache[n], 0);
|
|
|
|
for (b = 0; b < MAX_BRANCH; b++)
|
|
for (r = 0; r < n; r++)
|
|
mpz_add(bcache[n], bcache[n], rcache[n][b][r]);
|
|
}
|
|
|
|
void calc_unrooted(int n)
|
|
{
|
|
int b, r;
|
|
|
|
for (b = 0; b <= MAX_BRANCH; b++) {
|
|
mpz_t *p = malloc(sizeof(mpz_t) * n);
|
|
rcache[n][b] = p;
|
|
for (r = 0; r < n; r++) {
|
|
mpz_init(p[r]);
|
|
calc_rooted(p[r], n, b, r);
|
|
}
|
|
}
|
|
|
|
calc_first_branch(n);
|
|
|
|
mpz_init_set_ui(ucache[n], 0);
|
|
for (r = 0; r * 2 < n; r++)
|
|
for (b = 0; b <= MAX_BRANCH; b++)
|
|
mpz_add(ucache[n], ucache[n], rcache[n][b][r]);
|
|
|
|
if (!(n & 1)) {
|
|
mpz_add_ui(rtmp1, bcache[n/2], 1);
|
|
mpz_mul(rtmp1, rtmp1, bcache[n/2]);
|
|
mpz_divexact_ui(rtmp1, rtmp1, 2);
|
|
mpz_add(ucache[n], ucache[n], rtmp1);
|
|
}
|
|
}
|
|
|
|
void init(void)
|
|
{
|
|
mpz_init(tmp1), mpz_init(tmp2);
|
|
mpz_init(rtmp1), mpz_init(rtmp2);
|
|
}
|
|
|
|
int main(void)
|
|
{
|
|
int i;
|
|
|
|
init();
|
|
|
|
for (i = 0; i <= MAX_N; i++) {
|
|
calc_unrooted(i);
|
|
gmp_printf("%d: %Zd\n", i, ucache[i]);
|
|
}
|
|
|
|
return 0;
|
|
}
|