Cod sursa(job #1760681)

Utilizator LucianTLucian Trepteanu LucianT Data 21 septembrie 2016 08:40:12
Problema Arbori Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>
#define maxN 100
#define MOD 666013
using namespace std;
int dp[maxN][maxN][maxN];
long long comb;
int n,m,i,j,k,k1,x;
inline int modulo(int x)
{
    x%=m;
    while(x<0)
        x+=m;
    return x;
}
int main()
{
    freopen("arbori.in","r",stdin);
    freopen("arbori.out","w",stdout);
    scanf("%d %d %d",&n,&m,&k);
    for(i=0;i<=n;i++)
        dp[1][0][i]=1;
    for(i=2;i<=n;i++)
    {
        dp[i][modulo(i-1)][1]=1;
        for(k1=2;k1<=n;k1++)
            for(j=0;j<m;j++)
            {
                comb=1LL;
                for(x=0;x*k1<i;x++)
                {
                    dp[i][j][k1]+=comb*dp[i-x*k1][modulo(j-x)][k1-1];
                    comb*=dp[k1][modulo(k-1)][k1-1]+x;
                    comb/=x+1;
                }
            }
    }
    printf("%d",dp[n][k][n-1]);
    return 0;
}