Cod sursa(job #466408)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 26 iunie 2010 16:02:56
Problema Permutari2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <cstring>
#define MOD 10007
#define MAXN 310
using namespace std;

int N,K;

int D1[MAXN][MAXN];
int D2[MAXN][MAXN];


int main(){

	freopen("permutari2.in","r",stdin);
	freopen("permutari2.out","w",stdout);

	scanf("%d%d",&N,&K);

	fclose(stdin);

	memset(D1,0,sizeof(D1));

	for (int i=2;i<=N;++i)

		D1[1][i]=1;

	for (int i=2;i<=N;++i)
		for (int j=i+1;j<=N;++j){
			D1[i][j]=0;

			for (int other=i;other<=j;++other)
				if (other<j) {
					D1[i][j]+=D1[i-1][other];
					if (D1[i][j]>=MOD) D1[i][j]-=MOD;
				} else {
					D1[i][j]+=(other-(i-1))*D1[i-1][other];
					D1[i][j]%=MOD;
				}
		}

	D1[0][1]=1;

	memset(D2,0,sizeof(D2));

	D2[0][0]=1;

	for (int i=1;i<=N;++i){
		int lsup=K;
		if (i<K) lsup=i;
		for (int grd=1;grd<=lsup;++grd){
			D2[i][grd]=0;
			for (int ref=0;ref<i;++ref)
				if (D2[ref][grd-1]>0){
					int nstill=i-ref;
					D2[i][grd]+=D1[nstill-1][nstill]*D2[ref][grd-1];
					D2[i][grd]%=MOD;
				}
		}
	}

	printf("%d\n",D2[N][K]);


	fclose(stdout);

	return 0;
}