Pagini recente » Cod sursa (job #3160843) | Cod sursa (job #428957) | Arhiva de probleme | Cod sursa (job #141479) | Cod sursa (job #132552)
Cod sursa(job #132552)
Utilizator |
Mircea Pasoi domino |
Data |
6 februarie 2008 01:46:11 |
Problema |
Arbori |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
0.91 kb |
#include <stdio.h>
#include <string.h>
#define FIN "arbori.in"
#define FOUT "arbori.out"
#define MAX_N 95
#define MAX_M 15
#define ll long long
int N, M, K;
ll mem[MAX_N][MAX_M][MAX_N];
ll C(ll n, ll k)
{
ll i, ret = 1;
for (i = 1; i <= k; ++i)
ret *= n-k+i, ret /= i;
return ret;
}
ll solve(int n, int cnt, int size)
{
int i;
ll &ret = mem[n][cnt][size];
if (n == 1 && cnt == 0) return 1;
if (ret != -1) return ret;
if (size >= n) return 0;
ret = 0;
for (i = 0; i*size < n; ++i)
ret += solve(n-i*size, (cnt+M-i%M)%M, size+1)*C(solve(size, (K+M-1)%M, 1)+i-1, i);
return ret;
}
int main(void)
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d %d %d", &N, &M, &K);
memset(mem, -1, sizeof(mem));
mem[1][(K+M-1)%M][1] = 1;
printf("%lld\n", solve(N, K, 1));
return 0;
}