Pagini recente » Profil FMI_BreazCatalin | Cod sursa (job #2018149) | Cod sursa (job #689931) | Cod sursa (job #1783820) | Cod sursa (job #137540)
Cod sursa(job #137540)
#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;
}