Cod sursa(job #1727931)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 11 iulie 2016 21:49:00
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin("arbori.in");
ofstream fout("arbori.out");

const int dim = 105;
const int maxMod = 25;

int n, mod, k;

long long dp[dim][maxMod][dim];

inline int modulo(int x) {

	x = x % mod;
	if (x < 0)
		x += mod;

	return x;

}

int main() {

	fin >> n >> mod >> k;

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

	for (int i = 2; i <= n; ++i) {

		dp[i][modulo(i - 1)][1] = 1;

		for (int kk = 2; kk <= n; ++kk) {

			for (int j = 0; j < mod; ++j) {

				long long comb = 1;
				
				for (int l = 0; l * kk < i; ++l) {
					
					dp[i][j][kk] += comb * dp[i - l * kk][modulo(j - l)][kk - 1];
					
					comb *= dp[kk][modulo(k - 1)][kk - 1] + l;
					comb /= l + 1;
				
				}

			}

		}

	}

	fout << dp[n][k][n - 1] << '\n';

	return 0;

}

//Trust me, I'm the Doctor!