Cod sursa(job #2246562)

Utilizator cristina_borzaCristina Borza cristina_borza Data 27 septembrie 2018 10:48:16
Problema Permutari2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("permutari2.in");
ofstream g ("permutari2.out");

const int Mod = 10007;

int fact[500], dp[500][500], aux[500];
int n, K;

int main() {
    f >> n >> K;
    fact[0] = 1;
    for (int i = 1; i <= n; ++ i) {
        fact[i] = (fact[i - 1] * i) % Mod;
    }

    aux[1] = 1;
    dp[1][1] = 1;

    for (int i = 2; i <= n; ++ i) {
        aux[i] = fact[i];
        for (int j = 1; j < i; ++ j) {
            aux[i] = aux[i] - (fact[j] * aux[i - j]) % Mod;
            aux[i] = (aux[i] + Mod) % Mod;
        }

        dp[i][1] = aux[i];
    }

    for (int i = 2; i <= n; ++ i) {
        for (int j = 1; j < i; ++ j) {
            for (int k = 2; k <= min (i, K); ++ k) {
                dp[i][k] += dp[j][k - 1] * dp[i - j][1];
                dp[i][k] %= Mod;
            }
        }
    }

    g << dp[n][K] << '\n';
    return 0;
}