Cod sursa(job #2548746)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 16 februarie 2020 23:03:57
Problema Arbori Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 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 = 1; 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][n][(k - 1 + m) % m] + j) / (j + 1);
				}
			}
	}
	g << dp[n][n][k];
}