Cod sursa(job #2631170)

Utilizator betybety bety bety Data 29 iunie 2020 11:55:14
Problema Arbori Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb

#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;

}