Cod sursa(job #137392)

Utilizator mariusdrgdragus marius mariusdrg Data 17 februarie 2008 11:55:20
Problema Arbori Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.77 kb
#include<stdio.h>
#define LL long long
const int maxn = 95;

LL a[2][maxn][maxn],comb[maxn][maxn];
int i,j;
int nr,N,M,k;
LL l;
LL x;
LL ans;

int main()
{
        freopen("arbori.in","r",stdin);
        freopen("arbori.out","w",stdout);
        scanf("%d %d %d",&N,&M,&k);
        comb[0][0] = 1;
        for(i = 1;i <= N; ++i)
        {
                for(j = 0;j <= i; ++j)
                {
                        comb[i][j] += comb[i - 1][j];
                        if (j != 0) comb[i][j] += comb[i - 1][j - 1];
                }
        }
        int aux = 0;
        a[0][1][1] = 1;
        for(nr = 1;nr <= N; ++nr)
        {
                for(i = 1;i <= N; ++i)
                {
                        for(j = 1;j <= N; ++j)
                        {
                                if (a[aux][i][j] == 0) continue;
                                for(l = 1;l <= j; ++l)
                                {
                                        int x1 = 1;
                                        if (nr == 1) x1 = 0;
                                        if  (i + l * (k - x1) > N) break;
                                        for(x = 0 ;x <= l; ++x)
                                        {
                                                if(i + l * (k - x1) + x * M > N ) break;
                                                a[aux ^ 1][i + l * (k - x1) + x * M][l * (k - x1) + x * M] += (LL)a[aux][i][j] * comb[j][l] * comb[l][x];
                                        }
                                }
                        }
                }
                aux ^= 1;
                for(i = 1;i <= N; ++i) for(j = 1;j <= N; ++j) a[aux ^ 1][i][j] = 0;
                for(i = 1;i <= N; ++i) ans += a[aux][N][i];
        }

        printf("%lld\n",ans);



        return 0;
}