Cod sursa(job #479040)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 22 august 2010 00:26:08
Problema Arbori Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>

#define file_in "arbori.in"
#define file_out "arbori.out"

#define ll long long

int N,M,K;
ll a[93][12][12];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &N, &M, &K);
}

ll comb(ll n, ll k)
{
    int i;
	ll rez=1;

    for (i=1;i<=k;++i)
    {
		rez*=n-k+i;
	    rez/=i;
	}
    return rez;
}

ll Nr(int k, int x)
{

    if(k==1)
        return 1;

    ll rez=comb(a[k][(K+M-1)%M][N]+x-1,x);   

    return rez;
}


void solve()
{
	int i,j,k,x;
	for(i=0;i<=N;i++) a[1][0][i]=1;
	for (i=2;i<=N;++i)
		 for (j=0;j<M;++j)
			  for (k=1;k<=N;++k)
				   for (x=0;x<=i/k;++x)
					    a[i][j][k]+=a[i-x*k][(j-x+M*x)%M][k-1]*Nr(k,x);
	printf("%d\n", a[N][K][N]);
}	

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}