Cod sursa(job #2183906)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 23 martie 2018 16:07:32
Problema Arbori Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 95;
const int MMAX = 15;
const int KMAX = 95;

long long dp[NMAX][MMAX][KMAX];

int main(void) {
    int n, m, p;
    in >> n >> m >> p;
    
    // un singur nod
    for (int i = 0; i < n; ++i)
        dp[1][0][i] = 1;
    
    // i noduri, i - 1 frunze
    for (int i = 2; i <= n; ++i)
        dp[i][(i - 1) % m][1] = 1;
    
    for (int i = 2; i <= n; ++i)
    for (int k = 1; k <= n - 1; ++k)
    for (int j = 0; j <= m - 1; ++j) {
        long long cmb = 1;
        
        for (int l = 0; l * k < i; ++l) {
            dp[i][j][k] += cmb * dp[i - l * k][(j - l + (m << 10)) % m][k - 1];
            cmb = cmb * (dp[k][(p - 1 + m) % m][k - 1] + l) / (l + 1);
        }
    }
    
    out << dp[n][p][n - 1] << endl;
    return 0;
}