Cod sursa(job #137661)

Utilizator gcosminGheorghe Cosmin gcosmin Data 17 februarie 2008 12:53:07
Problema Arbori Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 0.79 kb
#include <stdio.h>

#define LL long long

int N, M, K;

LL din[100][100][100];

LL bun[100];

int main()
{
	int i, j, k, q;

	LL rez = 0;

	freopen("arbori.in", "r", stdin);
	freopen("arbori.out", "w", stdout);

	scanf("%d %d %d", &N, &M, &K);

	int vbun = K - 1;
	if (vbun < 0) vbun += M;

	bun[1] = 1;
	for (i = 0; i <= N; i++) din[1][0][i] = 1;

	LL nrpos;
	for (i = 2; i <= N; i++) {
		for (j = 1; j <= i - 1; j++) {
			for (k = 1; k <= N; k++) {
				din[i][j][k] = din[i][j][k - 1];

				nrpos = 1;
				for (q = 1; q <= j && q * k <= i; q++) {
					nrpos = nrpos * (bun[k] + q - 1) / q;
					din[i][j][k] += din[i - q * k][j - q][k-1] * nrpos;
				}
			}

			if (j % M == vbun) bun[i] += din[i][j][N];

			if (i == N && j % M == K) rez += din[i][j][N];
		}
	}

	printf("%lld\n", rez);

return 0;
}