uniolympiads Ελληνικά

Modular arithmetic and combinatorics

Fast exponentiation, inverses by Fermat's little theorem, and (nr)\binom{n}{r} in O(1)O(1) after O(n)O(n) preprocessing.

When

"Print the answer modulo 109+710^9 + 7". Almost every counting problem.

The idea

Exponentiation. aea^e with O(log⁡e)O(\log e) multiplications: write ee in binary, square aa at each bit, and multiply into the result those that correspond to set bits.

Inverse. For a prime pp and a≢0a \not\equiv 0, Fermat's little theorem gives ap−1≡1a^{p-1} \equiv 1, so

a−1≡ap−2(modp).a^{-1} \equiv a^{p-2} \pmod p .

This holds only for a prime modulus. For another modulus you need the extended Euclidean algorithm, and the inverse exists only if gcd⁡(a,m)=1\gcd(a, m) = 1.

Binomial coefficients. Precompute n!n! for n≤Nn \le N, and (N!)−1(N!)^{-1} with one exponentiation. Then go backwards: ((i−1)!)−1=(i!)−1⋅i((i-1)!)^{-1} = (i!)^{-1} \cdot i. So

(nr)=n!⋅(r!)−1⋅((n−r)!)−1\binom{n}{r} = n! \cdot (r!)^{-1} \cdot ((n-r)!)^{-1}

in O(1)O(1), with O(N)O(N) preprocessing and a single exponentiation.

The move that unlocks problems

Exponentiation II asks for abc mod pa^{b^c} \bmod p. bcb^c is huge, but by Fermat the exponent matters only modulo p−1p - 1: compute e=bc mod (p−1)e = b^c \bmod (p-1) and then ae mod pa^e \bmod p. (Careful when a≡0a \equiv 0.)

Distributing Apples: mm identical apples among nn children is (n+m−1m)\binom{n + m - 1}{m} (stars and bars).

Pitfalls

  • Every product of two numbers <109+7< 10^9 + 7 fits in long long (<1.01⋅1018< 1.01 \cdot 10^{18}, while the limit is 9.2⋅10189.2 \cdot 10^{18}). Three do not: reduce after every multiplication.
  • Subtraction gives a negative result: (a - b + MOD) % MOD.
  • binpow here also accepts a negative aa, and modulus 1 (where everything is 0). The test checks both.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/modular.cpp
// Modular arithmetic for a prime modulus: fast power, inverse (Fermat), binomial coefficients.
// binpow is O(log e); after initFactorials(N), nCr is O(1) for n <= N.

const ll MOD = 1000000007;

ll binpow(ll a, ll e, ll mod = MOD) {
    a %= mod;
    if (a < 0) {
        a += mod;
    }
    ll result = 1 % mod;
    while (e > 0) {
        if (e & 1) {
            result = result * a % mod;
        }
        a = a * a % mod;
        e >>= 1;
    }
    return result;
}

// a^(p-2) is the inverse of a modulo a prime p, for a not divisible by p.
ll inverse(ll a, ll mod = MOD) {
    return binpow(a, mod - 2, mod);
}

vector<ll> fact;
vector<ll> invFact;

void initFactorials(int maxN) {
    fact.assign(maxN + 1, 1);
    invFact.assign(maxN + 1, 1);
    for (int i = 1; i <= maxN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invFact[maxN] = inverse(fact[maxN]);
    for (int i = maxN; i >= 1; i--) {
        invFact[i - 1] = invFact[i] * i % MOD;
    }
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) {
        return 0;
    }
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

Tested on 20,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.