Cod sursa(job #132554)

Utilizator dominoMircea Pasoi domino Data 6 februarie 2008 01:47:42
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;
}