Cod sursa(job #178858)

Utilizator moga_florianFlorian MOGA moga_florian Data 15 aprilie 2008 12:19:07
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>

long long A[100][12][100];
int N,M,K;

long long Nr(int k, int x){

    if(k==1)
        return 1;

    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;

    //    A[0][0][0] = 1;

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

                if(i==2 && j==1 &&k==1){
                    int q = j;
                    q+=i;
                }

                for(int x = 0; x <= i/k; x++){
                    int ii,jj,kk;
                    ii = i-x*k;
                    jj = (j+M*x-x)%M;
                    kk = k-1;

                    A[i][j][k] += A[ii][jj][kk] * Nr(k,x);
                }

                //A[i][j][k] += A[i][j][k-1];

            }
/*
    for(int i=1;i<=N;i++)
        for(int j=0;j<M;j++){
            fprintf(fout,"%d %d -> ",i,j);
            for(int k=1;k<=N;k++)
                fprintf(fout,"%lld ",A[i][j][k]);
            fprintf(fout,"\n");
        }
*/
    fprintf(fout,"%lld\n",A[N][K][N]);

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

}