Cod sursa(job #563846)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 26 martie 2011 10:45:39
Problema Arbori Scor 100
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);

	for (int i = 0; i <= n; ++i)
		dp[1][0][i] = 1;

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

		for (int k = 2; k <= n; ++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;
}