Mai intai trebuie sa te autentifici.
Cod sursa(job #606463)
Utilizator | Data | 4 august 2011 14:14:04 | |
---|---|---|---|
Problema | Arbori | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.94 kb |
# include <cstdio>
typedef long long ll;
const char *FIN = "arbori.in", *FOU = "arbori.out";
const int MAX_N = 101, MAX_M = 21;
int N, M, K;
ll dp[MAX_N][MAX_M][MAX_N];
inline int mod (int A) {
if (A >= M || -A >= -M) A -= M;
if (A >= M || -A >= -M) A %= M;
if (A < 0) A += M;
return A;
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d %d %d", &N, &M, &K);
for (int i = 0; i <= N; ++i)
dp[1][0][i] = 1;
for (int i = 2; i <= N; ++i) {
dp[i][mod (i - 1)][1] = 1;
for (int k = 2; k <= N; ++k)
for (int j = 0; j < M; ++j) {
ll sol = 1;
for (int l = 0; l * k < i; ++l) {
dp[i][j][k] += sol * dp[i - l * k][mod (j - l)][k - 1];
sol *= dp[k][mod (K - 1)][k - 1] + l, sol /= l + 1;
}
}
}
fprintf (fopen (FOU, "w"), "%lld", dp[N][K][N - 1]);
}