Cod sursa(job #1013832)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 21 octombrie 2013 19:47:26
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <fstream>
#include <algorithm>


const int max1 = 100;
const int max2 = 20;

int n, m, K;
long long dp[max1][max2][max1];

int getMod(int x)
{
    int res = x % m;
    if (res < 0)
        res += m;
    return res;
}

int main() {
    freopen("arbori.in", "r", stdin);
    freopen("arbori.out", "w", stdout);

    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][getMod(i-1)][1] = 1;

        for (int k = 2; k <= n; ++k)
            for (int j = 0; j < m; ++j)
                {
                long long cmb = 1;
                for (int p = 0; p*k < i; ++p)
                {
                    dp[i][j][k] += dp[i - k * p][getMod(j - p)][k - 1] * cmb;
                    cmb *= dp[k][getMod(K - 1)][k - 1] + p;
                    cmb /= p+1;
                }
            }
    }

    printf("%lld\n", dp[n][K][n-1]);

    return 0;
}