Как вычислить C(n, k) для больших n по простому модулю через факториалы и обратные?
В задаче нужно много раз считать число сочетаний C(n, k) по модулю m = 1e9+7, при n до 2*10^5. Если в лоб перемножать n!/(k!(n-k)!), получаю переполнение и деление по модулю не работает. Как правильно предподсчитать факториалы и обратные факториалы, чтобы каждый запрос был за O(1)?
2 ответа
Деление по простому модулю заменяется умножением на обратный элемент: a/b ≡ a * b^(p-2) mod p (малая теорема Ферма). Идея — один раз предподсчитать массив факториалов fact[i] = i! mod p и массив обратных факториалов inv_fact[i] = (i!)^{-1} mod p. Тогда C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k].
Ключевой трюк для обратных факториалов за O(n): сначала считаем inv_fact[N] через быстрое возведение, а дальше идём вниз по тождеству inv_fact[i] = inv_fact[i+1] * (i+1).
const int MOD = 1e9 + 7;
const int N = 200001;
long long fact[N], inv_fact[N];
long long power(long long a, long long b, long long m) {
long long r = 1; a %= m;
while (b) { if (b & 1) r = r * a % m; a = a * a % m; b >>= 1; }
return r;
}
void precompute() {
fact[0] = 1;
for (int i = 1; i < N; i++) fact[i] = fact[i-1] * i % MOD;
inv_fact[N-1] = power(fact[N-1], MOD-2, MOD);
for (int i = N-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
long long C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}
Предподсчёт — O(n) умножений плюс один O(log p) на возведение в степень. Каждый запрос C(n,k) — O(1). Память O(n). Обязательно long long для произведений и не забывай брать % MOD после каждого умножения.
Частая грабля: не проверяешь k < 0 || k > n и обращаешься к fact[n] при n вне диапазона предподсчёта — это UB / выход за массив. Всегда возвращай 0 в этих случаях.
Ещё нюанс: малая теорема Ферма для обратного работает только если MOD — простое и не делит число. 1e9+7 и 998244353 — простые, тут всё ок. Если модуль составной, обратного через Ферма не получить — нужен расширенный Евклид (и обратный существует только при gcd(a, MOD)=1).