Cod sursa(job #138522)

Utilizator victorsbVictor Rusu victorsb Data 18 februarie 2008 19:40:54
Problema Arbori Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>

#define Nmax 95
#define Mmax 16
#define ll long long

int n, m, r;
ll D[2][Nmax][Mmax];
ll C[Nmax];

void citire()
{
	scanf("%d %d %d\n", &n, &m, &r);
}

ll calc(ll N, int K)
{
	if (K == 0) return 1;

	ll rez = calc(N - 1, K - 1);
	rez = rez * N / K;

	return rez;
}

void solve()
{
	int i, j, k, nr, step = 1;
	ll Comb;

	C[1] = 1;
	D[0][0][0] = 1;

	for (i = 1; i < n; ++i, step = !step)
	{
        for (j = 0; j <= n; ++j)
			for (k = 0; k < m; ++k)
				D[step][j][k] = D[!step][j][k];

		for (j = 0; j <= n; ++j)
			for (nr = 1; j + nr * i <= n; ++nr)
			{
				if (C[i])
					Comb = calc(C[i] + nr - 1, nr);
				else
					Comb = 0;

				for (k = 0; k < m; ++k)
					D[step][j + nr * i][(k + nr) % m] += D[!step][j][k] * Comb;
			}

		C[i + 1] = D[step][i][r == 0 ? m - 1 : r - 1];
	}

	printf("%lld\n", D[step][n - 1][r]);
}

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

	citire();
	solve();

	return 0;
}