Cod sursa(job #176211)

Utilizator sealTudose Vlad seal Data 10 aprilie 2008 20:52:28
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#define Nm 91
#define Mm 10
#define ll long long
#define mod(a) ((a)<0?(a)+m:(a))
int n,m,k;
ll M[Nm][Mm][Nm];

void read()
{
    freopen("arbori.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
}

void solve()
{
    int i,r,j,l,r2;
    long long comb,x;

    for(i=1;i<=n;++i)
        for(r=0;r<m;++r)
            for(j=n;j;--j)
            {
                if(i==1) { M[i][r][j]=!r; continue; }
                if(j>=i) continue;
                M[i][r][j]=M[i][r][j+1]; comb=1;
                x=j>1?M[j][mod(k-1)][1]:1;
                if(!x) continue;
                for(r2=mod(r-1),l=1;l*j<i;++l,r2=mod(r2-1))
                {
                    comb=comb*(x+l-1)/l;
                    M[i][r][j]+=comb*M[i-l*j][r2][j+1];
                }
            }
}

void write()
{
    freopen("arbori.out","w",stdout);
    printf("%lld\n",M[n][n>1?k:0][1]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}