Комбинаторика по модулю

Половина комбинаторных задач заканчивается словами «выведите ответ по модулю $10^9+7$». Причина проста: ответы вроде $\binom{200000}{100000}$ — числа в шестьдесят тысяч цифр, и хранить их незачем.

Считать биномиальные коэффициенты по модулю умеют двумя способами, и выбор между ними определяется размером $n$.

Когда n мало: треугольник Паскаля

При $n$ до пары тысяч проще всего заполнить таблицу по рекуррентности $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$:

vector<vector<long long>> c(n + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= n; i++) {
    c[i][0] = 1;
    for (int k = 1; k <= i; k++)
        c[i][k] = (c[i - 1][k - 1] + c[i - 1][k]) % MOD;
}

Плюс — работает при любом модуле, даже составном: здесь только сложение. Минус — $O(n^2)$ времени и памяти, дальше нескольких тысяч не масштабируется.

Когда n велико: факториалы

Основная схема. Предподсчитываем факториалы и обратные к ним, дальше каждый коэффициент — два умножения.

$$\binom{n}{k} = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \bmod p$$

const long long MOD = 1000000007;
const int N = 200001;
long long fact[N], invFact[N];

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

void build() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    invFact[N - 1] = power(fact[N - 1], MOD - 2, MOD);
    for (int i = N - 1; i > 0; i--) invFact[i - 1] = invFact[i] * i % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

Здесь есть один приём, ради которого стоит читать код внимательно.

Обратные факториалы за один проход

Наивно обратный к каждому факториалу считается возведением в степень: $N$ факториалов по $O(\log p)$ — это $2 \cdot 10^5 \cdot 30 = 6 \cdot 10^6$ операций. Терпимо, но лишнее.

Правильный ход: посчитать возведением в степень только последний обратный, а дальше идти справа налево по тождеству

$$\frac{1}{(i-1)!} = \frac{1}{i!} \cdot i$$

Один power на всю подготовку вместо $N$ штук. Строка invFact[i - 1] = invFact[i] * i % MOD — это ровно оно.

Проверка, что всё собралось верно: должно выполняться fact[i] * invFact[i] % MOD == 1 для каждого $i$, и invFact[0] == 1.

Что важно помнить про модуль

Схема с обратными факториалами требует, чтобы модуль был простым и больше $n$. Оба условия существенны.

Простота нужна, чтобы работала малая теорема Ферма. Если модуль составной, обратного к некоторым числам просто не существует.

Условие $p > n$ нужно, чтобы факториал не обнулился: как только в $n!$ попадает множитель $p$, весь факториал становится нулём по модулю, и никакой обратный его не воскресит. Для $p = 10^9+7$ и $n$ до $10^6$ это не проблема, а вот при модуле вроде $1000003$ и $n = 10^7$ — уже да. Такие случаи решает теорема Люка: коэффициент считают по цифрам $n$ и $k$ в системе счисления с основанием $p$ и перемножают.

Типовые формулы

Что чаще всего приходится выражать через $\binom{n}{k}$:

задача	формула
выбрать $k$ из $n$	$\binom{n}{k}$
упорядоченный выбор $k$ из $n$	$n! / (n-k)!$
сочетания с повторениями	$\binom{n + k - 1}{k}$
пути в сетке $n \times m$ вправо-вверх	$\binom{n+m}{n}$
разложить $n$ на $k$ неотрицательных слагаемых	$\binom{n + k - 1}{k - 1}$
перестановки с повторами	$n! / (a_1! \cdot a_2! \cdots)$

Отдельно стоит запомнить два тождества, потому что они превращают квадратичный перебор в один коэффициент:

$$\sum_{k=0}^{n} \binom{n}{k} = 2^n, \qquad \sum_{k} \binom{n}{k}\binom{m}{r-k} = \binom{n+m}{r}$$

Формула включений-исключений

Спутник комбинаторики по модулю. Когда «посчитать напрямую» не выходит, считают все варианты и вычитают плохие:

$$|A_1 \cup \dots \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + \sum |A_i \cap A_j \cap A_k| - \dots$$

Практический вид — сумма по подмножествам со знаком $(-1)^{|S|}$. Если множеств до 20, перебираются все $2^n$ масок; если групп немного и они однотипны, сумма сворачивается в один цикл.

Типичный пример — количество путей в сетке с запрещёнными клетками: считаем все пути, вычитаем проходящие через первое препятствие, добавляем прошедшие через два, и так далее.

Важная деталь при работе по модулю: вычитание может уйти в минус. Каждый раз после - нужно нормализовать: answer = ((answer - bad) % MOD + MOD) % MOD. Забытая нормализация даёт отрицательный ответ, который судья не примет, — и найти её тяжело, потому что на маленьких тестах она обычно не проявляется.