Cod sursa(job #2246549)

Utilizator cristina_borzaCristina Borza cristina_borza Data 27 septembrie 2018 10:40:17
Problema Permutari2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 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];
int n, K;

int aux[] = {0, 1, 1, 3, 13, 71, 461, 3447, 9079, 3154, 7351, 6524, 9235, 3261, 223, 646, 7963, 6624, 8028, 5532, 1792, 4542, 5498, 1914, 942, 2853, 8124, 8773, 7243, 2700, 1070, 3396, 239, 5737, 2784, 2677, 9476, 870, 2210, 1219, 9307, 9936, 4143, 4997, 5932, 9585, 6779, 4841, 4169, 3724, 6777, 8689, 3678, 8725, 3835, 6574, 6233, 4084, 9710, 8846, 6244, 35, 4567, 3166, 8192, 4345, 332, 973, 7706, 7978, 2230, 5851, 6235, 3282, 3376, 2935, 3172, 3599, 5752, 2353, 5876, 7492, 5801, 5518, 5050, 6776, 7243, 3635, 2886, 2152, 7580, 3533, 5689, 2493, 8324, 3193, 5581, 7624, 5409, 943, 7995, 1668, 1186, 5456, 4757, 2909, 2142, 3703, 7488, 9725, 3857, 5045, 573, 7789, 6536, 5891, 6878, 2326, 7045, 1079, 5084, 7069, 8698, 6081, 7656, 3096, 7456, 4897, 5658, 5000, 3954, 9299, 2491, 6086, 2368, 5922, 4570, 1421, 6311, 1251, 6221, 762, 3172, 865, 6603, 8219, 1233, 7012, 3586, 4857, 9512, 565, 3774, 588, 6181, 3822, 1685, 5702, 3914, 8392, 3785, 9751, 6261, 5003, 4104, 1118, 5321, 3168, 7683, 9036, 2444, 6523, 6010, 5228, 6143, 3995, 2314, 6969, 7568, 3459, 5280, 573, 5918, 3137, 4048, 7176, 2148, 3442, 2835, 8943, 1888, 1066, 1437, 5907, 9954, 9056, 7161, 2574, 4964, 9440, 2605, 9452, 1388, 1916, 5054, 7337, 4449, 7256, 7592, 9546, 8101, 6890, 2132, 7086, 2866, 6296, 4671, 1941, 3647, 4321, 590, 9231, 4753, 2868, 6186, 710, 4967, 1570, 2861, 711, 2353, 1091, 2063, 5016, 9089, 5914, 9426, 4745, 3092, 8071, 3182, 9974, 8357, 7132, 3324, 6970, 5358, 3690, 7014, 838, 5265, 474, 8690, 9948, 7430, 1147, 2949, 7629, 7384, 5737, 1622, 9231, 4674, 5305, 1781, 1278, 4149, 4149, 2422, 3201, 1410, 7962, 7879, 5623, 9614, 7462, 7749, 1306, 2458, 4778, 2556, 559, 1652, 4078, 4406, 8645, 1201, 9203, 6523, 6652, 4885, 3581, 9757, 6308, 6396, 225, 7323, 7078, 1279, 6015, 7161};

int main() {
    f >> n >> K;

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

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

    }

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