Cod sursa(job #514571)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 19 decembrie 2010 10:42:17
Problema Permutari2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <stdio.h>
#define Nmax 305
#define Mod 10007

int din[Nmax][Nmax];
int N,K;

int main(){
    int i,j,k,f;
    freopen("permutari2.in","r",stdin);
    freopen("permutari2.out","w",stdout);
    scanf("%d%d",&N,&K);
    din[1][1]=1; f=1;

    for(i=2;i<=N;++i){
        din[i][1]=f=(f*i)%Mod;

        for(j=2;j<=i ;++j){
            for(k=j-1; k<i; ++k)
                din[i][j]=(din[i][j]+din[k][j-1]*din[i-k][1]) % Mod;
            din[i][1]-=din[i][j];
            if( din[i][1]<0 ) din[i][1]+=Mod;
        }
    }

    printf("%d\n",din[N][K]);
    fclose(stdin); fclose(stdout);
    return 0;
}