Modular calculations

combinatorics.cpp

// modular constant
const int m = 1e10 + 7;
// array: x <-> inverse to x
int invs[maxN];

// number of combinations C_n^k
// uses `invs` array as memory
int c_n_k(const int n, const int k) {
  if (k > n) return 0;

  int res = 1;
  k = min(k, n - k);
  for (int i = 1; i <= k; ++i) {
    res = (res * (n - i + 1)) % mod;
    invs[i] = (invs[i])? invs[i] : inverse(i, mod);
    res = (res * invs[i]) % mod;
  }

  return res;
}

gcd.cpp

// (a, b)
int gcd(const int a, const int b) {
  return (b)? gcd(b, a % b) : a;
}

// finds x, y that ax + by = (a, b)
// returns (a, b)
int extended_gcd(const int a, const int b, int& x, int& y) {
  if (a % b == 0) {
    x = 0;
    y = 1;
    return b;
  }

  int g = extended_gcd(b, a % b, x, y);
  std::swap(x, y);
  y -= (a / b) * x;
 
  return g;
}

inverse.cpp

// return such x that
// ax = 1 (mod m)
int inverse(const int a, const int m) {
  int x, y;
  extended_gcd(a, m, x, y);
  return (x % m + m) % m;
}