Modular arithmetic and combinatorics
Fast exponentiation, inverses by Fermat's little theorem, and in after preprocessing.
When
"Print the answer modulo ". Almost every counting problem.
The idea
Exponentiation. with multiplications: write in binary, square at each bit, and multiply into the result those that correspond to set bits.
Inverse. For a prime and , Fermat's little theorem gives , so
This holds only for a prime modulus. For another modulus you need the extended Euclidean algorithm, and the inverse exists only if .
Binomial coefficients. Precompute for , and with one exponentiation. Then go backwards: . So
in , with preprocessing and a single exponentiation.
The move that unlocks problems
Exponentiation II asks for . is huge, but by Fermat the exponent matters only modulo : compute and then . (Careful when .)
Distributing Apples: identical apples among children is (stars and bars).
Pitfalls
- Every product of two numbers fits in
long long(, while the limit is ). Three do not: reduce after every multiplication. - Subtraction gives a negative result:
(a - b + MOD) % MOD. binpowhere also accepts a negative , 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.
// 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.
- Exponentiation · Mathematics
- Exponentiation II · Mathematics
- Binomial Coefficients · Mathematics
- Creating Strings II · Mathematics
- Distributing Apples · Mathematics
More in the USACO Guide
- Modular Arithmetic · usaco.guide/gold/modular
- Combinatorics · usaco.guide/gold/combo
In English, with more problems per level.