Cod sursa(job #1744649)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 20 august 2016 02:32:14
Problema Arbori Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;

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

const int MAXN = 110;
const int MAXM = 25;

int m;

long long dp[MAXN][MAXM][MAXN];

int Modulo(int value) {
    value %= m;
    if (value < 0)
        value += m;
    return value;
}

int main() {
    int n, k;
    cin >> n >> m >> 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 k0 = 2; k0 <= n; k0++)
            for (int j = 0; j < m; j++) {
                long long combinations = 1;
                for (int l = 0; l * k0 < i; l++) {
                    dp[i][j][k0] += combinations * dp[i - l * k0][Modulo(j - l)][k0 - 1];
                    combinations *= dp[k0][Modulo(k - 1)][k0 - 1] + l;
                    combinations /= l + 1;
                }
            }
    }
    cout << dp[n][k][n - 1] << "\n";
    return 0;
}