Cod sursa(job #137540)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 17 februarie 2008 12:36:29
Problema Arbori Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.2 kb
#include <cstdio>
#include <map>

using namespace std;

struct C {
	char a, b, c;

	C(char _a = 0, char _b = 0, char _c = 0): a(_a), b(_b), c(_c) {}

	bool operator<(const C &X) const {
		return a < X.a || (a == X.a && b < X.b) ||
			(a == X.a && b == X.b && c < X.c);
	}
};

const int NMAX = 128;
typedef long long llong;

int N, M, K, K1;
map <C, llong> S;
llong DP[NMAX], R;

void read(void) {
	FILE *fin = fopen("arbori.in", "rt");

	fscanf (fin, "%d %d %d", &N, &M, &K);

	fclose(fin);
}

llong back(char s, char e, char v) {
	if (s < e) return 0;
	if (v * e < s) return 0;
	if (s == 0 && e == 0) return 1;
	if (S.find(C(s, e, v)) != S.end())
		return S[C(s, e, v)];

	llong rez = 0;
	char cv = v;
	do {
		rez += DP[cv] * back(s-cv, e-1, cv);
	} while (--cv);

	return S[C(s, e, v)] = rez;
}

void solve(void) {
	int i, j;

	DP[1] = 1;
	K1 = K - 1;
	if (K1 < 0) K1 += M;

	for (i = 2; i < N; ++i)
		for (j = 1; j <= i; ++j)
			if (j % M == K1)
				DP[i] += back(i-1, j, i-1);
	
	for (j = 1; j <= N; ++j)
		if (j % M == K)
			R += back(N-1, j, N-1);
}

void write(void) {
	FILE *fout = fopen("arbori.out", "wt");

	fprintf(fout, "%lld\n", R);

	fclose(fout);
}

int main(void) {

	read();

	solve();

	write();

	return 0;
}