Pagini recente » Cod sursa (job #1183684) | Cod sursa (job #2823804) | Cod sursa (job #2309414) | Cod sursa (job #1383148) | Cod sursa (job #2631170)
#include <stdio.h>
#include <string.h>
#define BIGINT long long
#define fmt "%lld\n"
#define NMAX 128
BIGINT T[NMAX], T2[NMAX], CR[NMAX];
BIGINT ntrees[NMAX][NMAX];
int i, j, k, p, N, M, K, c, a;
inline BIGINT comb(BIGINT n, int k)
{
BIGINT res = 1;
int q;
for (q = 1; q <= k; q++)
res = (res * (n - (k - q))) / q;
return res;
}
int main()
{
freopen("arbori.in", "r", stdin);
scanf("%d %d %d", &N, &M, &K);
// initialize DP states
memset(ntrees, 0, sizeof(ntrees));
T[1] = T2[1] = 1;
ntrees[1][0] = 1;
// DP
// p = how many nodes are in the subtree of the last son of the tree root
for (p = 1; p <= N - 1; p++)
{
// combinations with repetitions
for (k = 1; k <= N; k++)
CR[k] = comb(T2[p] + (BIGINT)(k - 1), k);
// i = the total number of nodes in the tree
for (i = N; i >= p + 1; i--)
// j = the total number of sons the root has
for (j = 1; j < i; j++)
// k = the number of sons of the root which have p nodes in their subtree
for (k = 1; k <= j && k * p < i; k++)
ntrees[i][j] += ntrees[i - k * p][j - k] * CR[k];
// compute T[p+1]
T[p+1] = 0;
for (j = 1; j <= p; j++)
if (j % M == K)
T[p+1] += ntrees[p+1][j];
// compute T2[p+1]
T2[p+1] = 0;
for (j = 1; j <= p; j++)
if ((j % M) == ((K - 1 + M) % M))
T2[p+1] += ntrees[p+1][j];
//fprintf(stderr, "%d -> %I64d ; %I64d\n", p + 1, T[p + 1], T2[p + 1]);
}
freopen("arbori.out", "w", stdout);
printf(fmt, T[N]);
return 0;
}