Cod sursa(job #1914840)

Utilizator thewildnathNathan Wildenberg thewildnath Data 8 martie 2017 18:42:59
Problema Kperm Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>

const int NMAX = 5000;
const long long MOD = 666013;

long long fact[1 + NMAX];

int putere(long long val, int exp) {
  long long rez = 1;

  for (int i = 1; i <= exp; ++i)
    rez = (rez * val) % MOD;

  return rez;
}

int main() {
  freopen("kperm.in", "r", stdin);
  freopen("kperm.out", "w", stdout);

  fact[0] = 1;
  for (int i = 1; i <= NMAX; ++i)
    fact[i] = (fact[i - 1] * i) % MOD;

  long long n, k;

  scanf("%lld%lld", &n, &k);

  long long num_l = n % k;
  long long num_s = k - num_l;
  long long lung_l = (n + k - 1) / k;
  long long lung_s = n / k;

  long long sol =
    ((((fact[num_s] * fact[num_l]) % MOD) *
    (putere(fact[lung_s], num_s))) % MOD *
    (putere(fact[lung_l], num_l))) % MOD;

  printf("%lld\n", sol);

  return 0;
}

// x! * y! * [(n + k - 1) / k]!^x * [(n / k)!]^y