Факториал по модулю и предподсчёт: как считать C(n,k) mod p за O(1) на запрос?
Нужно отвечать на много запросов C(n, k) mod 10^9+7 при n, k до 2·10^5. Считать каждый раз произведение — медленно. Как организовать предподсчёт факториалов и обратных факториалов, чтобы каждый запрос был O(1)?
2 ответа
Стандартная схема: один раз за O(n + log p) предподсчитываешь массивы fact[] и inv_fact[], потом каждый C(n,k) за O(1).
const int MAXN = 200005;
const long long MOD = 1e9 + 7;
long long fact[MAXN], inv_fact[MAXN];
void precompute() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++)
fact[i] = fact[i-1] * i % MOD;
inv_fact[MAXN-1] = binpow(fact[MAXN-1], MOD-2, MOD); // Ферма, 1 раз
for (int i = MAXN-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;
}
Ключ — обратные факториалы считаются назад из соотношения inv_fact[i] = inv_fact[i+1] · (i+1), поэтому всего одно возведение в степень. Память O(n). Это базовый шаблон для комбинаторики на олимпиадах: через те же массивы получаешь размещения A(n,k) = fact[n]·inv_fact[n-k] и т.д.
Не забудь, что это работает корректно только если MOD простой и больше n (иначе среди 1..n встретится множитель, кратный MOD, и факториал «занулится» по модулю, обратного не будет). Для 10^9+7 и n ≤ 2·10^5 всё ок. Если модуль составной (например, 10^6 в редких задачах) — формула через обратные факториалы ломается, нужна теорема Люка или разложение модуля; но это уже экзотика.