Cod sursa(job #178807)

Utilizator moga_florianFlorian MOGA moga_florian Data 15 aprilie 2008 09:52:32
Problema Arbori Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>

long long A[128][16][128];
int N,M,K;

long long Nr(int k, int x){

    long long num = A[k][(K+M-1)%M][N] + x - 1;
    long long rez = 1;
    long long crt = 2;

    for(long long i = num - x + 1; i<= num; i++){
        rez *= i;
        while(crt <= x && rez%crt==0){
            rez/=crt;
            crt++;
        }
    }

    if(!rez)
        return 1;
    return rez;
}

int main(){

    FILE *fin = fopen("arbori.in","r"),
         *fout = fopen("arbori.out","w");

    fscanf(fin,"%d%d%d",&N,&M,&K);

    for(int k=0;k<=N;k++)
        A[1][0][k] = 1;


    for(int i=2;i<=N;i++)
        for(int j=0;j<M;j++)
            for(int k=1;k<=N;k++){

                for(int x = 0; x <= i/k; x++)
                    A[i][j][k] += A[i-x*k][(j+M-x) % M][k-1] * Nr(k,x);

            }

    fprintf(fout,"%lld\n",A[N][K][N]);

    fclose(fin);
    fclose(fout);
    return 0;

}