Cod sursa(job #764325)

Utilizator darrenRares Buhai darren Data 4 iulie 2012 19:04:36
Problema Arbori Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstring>
#include <cassert>
#include <fstream>
#include <algorithm>

using namespace std;

int N, M, K;
long long D[92][12][92];

long long getR(int nodes, int modul, int prev)
{
	if (nodes == 1 && modul == 0) return 1;
	if (nodes == 1) return 0;
	if (prev == 1 && (M + modul - (nodes - 1)) % M == 0) return 1;
	if (prev == 1)  return 0;
	
	long long& now = D[nodes][modul][prev];
	if (now != -1) return now;
	
	now = getR(nodes, modul, prev - 1);
	
	long long COMB = 1;
	for (int act = 1; act * prev < nodes; ++act)
	{
		COMB *= getR(prev, (M + K - 1) % M, prev - 1) + act - 1;
		COMB /= act;
		now += getR(nodes - prev * act, (M + modul - act) % M, prev - 1) * COMB;
	}
	
	return now;
}

int main()
{
	ifstream fin("arbori.in");
	ofstream fout("arbori.out");
	
	fin >> N >> M >> K;
	
	for (int i = 0; i <= N - 1; ++i)
		D[1][0][i] = 1;
	for (int i = 2; i <= N; ++i)
	{
		D[i][(M + i - 1) % M][1] = 1;
		for (int j = 0; j < M; ++j)
			for (int k = 2; k <= N; ++k)
			{
				D[i][j][k] = D[i][j][k - 1];
				if (k >= i) continue;
				
				long long COMB = 1;
				for (int act = 1; act * k < i; ++act)
				{
					COMB *= D[k][(M + K - 1) % M][k - 1] + act - 1;
					COMB /= act;
					D[i][j][k] += D[i - act * k][(M + j - act) % M][k - 1] * COMB;
				}
			}
	}
	
	fout << D[N][K][N - 1] << '\n';
	
	fin.close();
	fout.close();
}