Cod sursa(job #2548744)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 16 februarie 2020 22:57:03
Problema Arbori Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#define ll long long

const int nmax = 105;
const int mmax = 25;

ll dp[nmax][nmax][mmax];

void init_dp(int n)
{
	for (int i = 0; i <= n; i++)
		dp[1][i][0] = 1LL;
}


int main()
{
	std::ifstream f("arbori.in");
	std::ofstream g("arbori.out");
	int n, m, k;
	f >> n >> m >> k;
	init_dp(n);
	for (ll i = 2; i <= n; i++) {
		dp[i][1][(i - 1) % m] = 1LL;
		for (ll ii = 2; ii <= n; ii++)
			for (ll rest = 0; rest < m; rest++) {
				ll ans = 1;
				for (ll j = 0; j * ii < i; j++) {
					dp[i][ii][rest] += ans * dp[i - j * ii][ii - 1][((rest - j) % m + m) % m];
					ans = (ans*dp[ii][ii - 1][(k - 1 + m) % m] + ii)/(ii+1);
				}
			}
	}
	g << dp[n][n - 1][k];
}