Cod sursa(job #137341)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 17 februarie 2008 11:21:28
Problema Arbori Scor 70
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.48 kb
#include <stdio.h>
#include <string.h>

#define BIGINT long long
#define fmt "%lld\n"

#define NMAX 128

BIGINT T[NMAX], T2[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++)
	{
		// 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] * 
					                comb(T2[p] + (BIGINT)(k - 1), k); // combinations with repetitions

		// 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;
}