Cod sursa(job #764329)

Utilizator darrenRares Buhai darren Data 4 iulie 2012 19:09:08
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 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 * 100 + 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 * 100 + K - 1) % M, prev - 1) + act - 1;
		COMB /= act;
		now += getR(nodes - prev * act, (M * 100 + modul - act) % M, prev - 1) * COMB;
	}
	
	return now;
}

int main()
{
	ifstream fin("arbori.in");
	ofstream fout("arbori.out");
	
	memset(D, -1, sizeof(D));
	
	fin >> N >> M >> K;
	fout << getR(N, K, N - 1) << '\n';
	
	fin.close();
	fout.close();
}