Cod sursa(job #563840)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 martie 2011 10:36:36
Problema Arbori Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>

const int MAXN = 100;
const int MAXM = 20;

int n, m, K;
long long dp[MAXN][MAXM][MAXN];

int getMod(int x) {
	int res = x % m;
	if (res < 0)
		res += m;
	return res;
}

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

	scanf("%d %d %d ", &n, &m, &K);

	dp[1][0][0] = 1;
	for (int i = 2; i <= n; ++i) {
		for (int p = 1; p < i; ++p) 
			dp[i][getMod(p)][1] += 1;

		for (int k = 2; k < i; ++k)
			for (int j = 0; j < m; ++j) {
				long long cmb = 1;
				for (int p = 0; p*k < i; ++p) {
					dp[i][j][k] += dp[i-k*p][getMod(j-p)][k-1]*cmb;
					cmb *= dp[k][getMod(K-1)][k-1]+p;
					cmb /= p+1;
				}
			}
	}

	printf("%lld\n", dp[n][K][n-1]);

	return 0;
}