Cod sursa(job #2773946)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 9 septembrie 2021 13:23:41
Problema Arbori Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
using namespace std;

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

long long comb (long long n, int k)
{
    int i;
    long long rasp = 1;
    for (i = 1; i<=k; i++)
        rasp = rasp * (n-i+1) / i;
    return rasp;
}

int main()
{
    int n, m, k, i, j, it, x;
    long long dp[100][100] = {};
    long long dpa[100] = {};
    long long combv[101];

    fin >> n >> m >> k;

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

    for (i = 2; i<=n; i++)
    {
        for (j = (k - (i != n) <= 0); j*m+k - (i != n) < i; j++)
            dpa[i] = dpa[i] + dp[j*m+k - (i != n)][i-1];

        for (j = 1; j<=n; j++)
            combv[j] = comb(dpa[i] + j - 1, j);

        for (x = n/i; x>=1; x--)
            for (j = n; j>=x; j--)
                for (it = x*i; it<=n; it++)
                    dp[j][it] = dp[j][it] + dp[j-x][it-x*i] * combv[x];
    }
    fout << dpa[n];
    return 0;
}