modular_arithmetic.md

Modular Arithmetic

(a +|-|* b) % m = (a % m + b % m) % m

Something extra for / (division).

Mostly in programming contests, MOD = 10^9 + 7 (1000000007), which is the smallest 10 digit prime number.

Modular Inverse (/)

(1 / a) mod M; For this, gcd(a, M) = 1 is a mandatory condition, both a and M must be co primes;

Fermat's Little Theorem (Primes as MOD)

a^(-1) mod M = a^(M - 2) mod M (M is a prime here)

a mod M = a^M mod M
a^0 mod M = a ^ (M - 1) mod M

-1 % 3 = 2

(a % m - b % m + m) % m

(5 mod 4 - 3 mod 4 + 3) mod 3 = 1 (negative image is -2)

-x % m = (-x + m) % m

0 <= |image| <= m - 1

c(n, k) = c(n - 1, k) + c(n - 1, k - 1)
Dynamic Programming Approach

int c[n][n];

// c[0][i] = 0; for all i
// c[i][0] = 1; for all i

// O(n^2)
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
    }
}

We also know that
c(n, k) = n! / ((k!).(n - k)!)

fact[n], inv[n]
fact[0] = fact[1] = 1
inv[0] = inv[1] = 1
for all i:
    fact[i] = fact[i - 1] * i
    inv[i] = inverse(fact[i])
// O(n.log(m)), log(m) factor because of computing modular inverse
// It takes O(log(m)) time to exponentiate fact[i] to (m - 2)
// using binary exponentiation (square and multiply technique)

c(n, k) = fact[n] * inv[k] % m * inv[n - k] % m;