Cod sursa(job #2510728)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 17 decembrie 2019 11:23:19
Problema Permutari2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>

const int MAX_N = 300;
const int MOD = 10007;

long long Count[5 + MAX_N][5 + MAX_N];

int main() {

  std::ifstream fin("permutari2.in");
  int n, k;
  fin >> n >> k;
  Count[1][1] = 1;
  long long fact = 1;
  for (int i = 2; i <= n; i++) {
    fact = (fact * i) % MOD;
    Count[i][1] = fact;
    for (int j = 2; j <= i; j++) {
      long long val = 0;
      for (int x = j - 1; x < i; x++)
        val += Count[x][j - 1] * Count[i - x][1];
      Count[i][j] = val - val / MOD * MOD;
      Count[i][1] = (Count[i][1] - Count[i][j] + MOD) % MOD;
    }
  }

  std::ofstream fout("permutari2.out");
  fout << Count[n][k];

  return 0;
}