Cod sursa(job #1359919)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 25 februarie 2015 09:45:00
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>

const int MAXN = 100;
const int MAXM = 20;

int n, m, K;
long long dp[MAXN][MAXM][MAXN];

int mod(int x) {
    int mode = x % m;
    if (mode < 0)
        mode += m;
    return mode;
}

int main()
{
    freopen("arbori.in", "rt", stdin);
    freopen("arbori.out", "wt", 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][mod(i-1)][1]=1;

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

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

    return 0;
}