Арифметика по модулю

Когда ответ «выведите по модулю $10^9 + 7$», задача обычно не про модуль — просто настоящий ответ не помещается ни в какой тип. Но правила обращения с остатками надо знать точно, иначе аккуратная формула даст неверное число.

Что можно и чего нельзя

Сложение, вычитание и умножение с остатками работают как обычно:

$$(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$$

То же для разности и произведения. Деления в этом списке нет — про него отдельно.

Практически это значит, что брать остаток можно на каждом шаге, и результат не изменится. Так и надо делать: иначе промежуточные значения переполнятся.

const long long MOD = 1000000007;
long long result = 1;
for (long long value : a) result = result * value % MOD;

Произведение двух чисел до $10^9$ — это до $10^{18}$, что помещается в long long, но едва. Поэтому long long здесь обязателен, а int даст молчаливое переполнение.

Отрицательные остатки

В C++ остаток от деления отрицательного числа отрицателен: (-7) % 3 даёт $-1$, а не $2$. В Python — наоборот, $2$.

Это ловушка при вычитании:

long long diff = (a - b) % MOD;          // может выйти отрицательным
long long ok = ((a - b) % MOD + MOD) % MOD;   // так безопасно

Формулы включения-исключения, где слагаемые вычитаются, ломаются на этом постоянно: ответ получается «почти правильный», но со сдвигом на модуль.

Быстрое возведение в степень

Считать $a^n$ умножением $n$ раз — линия. Есть способ за логарифм.

Идея: $a^n = (a^{n/2})^2$ для чётного $n$, и $a^n = a \cdot a^{n-1}$ для нечётного. Каждый шаг уменьшает степень вдвое.

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;
}

Это итеративная запись той же идеи: биты степени просматриваются от младшего к старшему, и в ответ домножается та степень основания, чей бит установлен.

В Python то же самое встроено: pow(base, exp, mod) — и работает быстро, потому что реализовано на C.

Деление по модулю

Разделить на $b$ по модулю — значит умножить на такое $b^{-1}$, что $b \cdot b^{-1} \equiv 1 \pmod m$. Это число называется обратным элементом.

Существует оно не всегда: только если $b$ и $m$ взаимно просты. Когда $m$ простое — а $10^9 + 7$ простое, — это выполнено для всех $b$, не кратных $m$.

Найти обратный проще всего малой теоремой Ферма: при простом $m$ верно $b^{m-1} \equiv 1$, откуда

$$b^{-1} \equiv b^{m-2} \pmod m$$

long long inverse(long long b, long long mod) { return power(b, mod - 2, mod); }

В Python с версии 3.8 работает pow(b, -1, mod).

Это стоит логарифм на каждое деление. Если делить приходится часто — например, считать много биномиальных коэффициентов, — обратные к факториалам считают заранее одним проходом.

Почему модуль именно такой

$10^9 + 7$ выбирают не случайно: оно простое (значит, есть обратные ко всему) и меньше $2^{30}$, так что произведение двух остатков помещается в 64 бита с запасом.

Иногда встречается $998244353$ — тоже простое, но с дополнительным свойством, полезным для быстрого преобразования Фурье. На олимпиадах школьного уровня разницы нет.