Modular Multiplicative Inverse

If we have a * x = 1 (mod kMod), we call x is a multiplicative inverse of a when modular is kMod (in this post, kMod is a prime number). Usually we use a^-1 to represent it.

Binary Exponentiation

Given a and kMod, we can get a^-1 in O(logkMod) time.

// a * x == 1 (mod kMod)
// according to Fermat's little theorem (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem)
// we have a * x == a^(kMod-1)
// so x == a^(kMod-2)

ll GetInverse(int val) { return FastPower(val, kMod - 2); }
ll FastPower(ll val, unsigned int n) {
  if (n == 0) {
    return 1;
  }
  if (n == 1) {
    return val;
  }
  if (n % 2 == 0) {
    return FastPower((val * val) % kMod, n / 2);
  }
  return (FastPower((val * val) % kMod, (n - 1) / 2) * val) % kMod;
}

Dynamic Programming

int GetInverse(int n) {
  inv[1] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = (ll)(kMod - kMod / i) * inv[kMod % i] % p;
  }
}

This solves inverse of [1, n] in linear time. See https://oi-wiki.org/math/inverse/#_5 for details.

prefix_mul[0] = 1;
for (int i = 1; i <= n; ++i) {
  prefix_mul[i] = prefix_mul[i - 1] * nums[i] % kMod;
}
prefix_mul_inverse[n] = GetInverse(prefix_mul[n], kMod - 2);
for (int i = n; i >= 1; --i) {
  // prefix_mul_inverse[i] = nums[0]^-1 * ... * nums[i]^-1
  // so prefix_mul_inverse[i] * nums[i] = nums[0]^-1 * ... * nums[i - 1]^-1
  prefix_mul_inverse[i - 1] = prefix_mul_inverse[i] * nums[i] % kMod;
}
for (int i = 1; i <= n; ++i) {
  // prefix_mul_inverse[i] = nums[0]^-1 * ... * nums[i]^-1
  // prefix_mul[i - 1] = nums[0] * ... * nums[i - 1]
  nums_inverse[i] = prefix_mul_inverse[i] * prefix_mul[i - 1] % kMod;
}