Cod sursa(job #1626990)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 3 martie 2016 13:26:05
Problema Arbori Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <cstdio>
#define MAXN 100

using namespace std;

int n, m, wanted;
int din[MAXN][MAXN][MAXN];
long long fact = 1;

int number(int p, int k)
{
	int val = k== 1 ? 1 : din[k][(wanted+m-1)%m][n];
	if (p) {
		fact *= (p+val-1);
		fact /= p;
	}
	else fact = 1;
    return fact;
}

void solve()
{
	for (int i = 0; i<= n; i++)
		din[1][0][i] = 1;
	//din[1][0][0] = 1;
    for (int i = 2; i <= n; i++) {
		din[i][(i-1)%m][1]=1;
        for (int rj = 0; rj < m; rj++) {
			int j = rj%m;
            for (int k = 2; k <= n; k++) {
				for (int p = 0; p*k < i; p++) {
					din[i][j][k] = (din[i][j][k] + din[i-(p*k)][(j-p+100*m)%m][k-1] * number(p, k));
				}
            }
        }
    }
    printf("%d", din[n][wanted][n]);
}

int main()
{
    freopen("arbori.in", "r", stdin);
    freopen("arbori.out", "w", stdout);

	scanf("%d %d %d", &n, &m, &wanted);
	solve();

    return 0;
}