Модульная арифметика в коде

Хеши целиком состоят из сложений и умножений по модулю. Как это написано, влияет и на скорость, и на количество ошибок.

Математическая сторона разобрана в статье про арифметику по модулю; здесь — про реализацию.

Сложение без остатка

Операция % дорогая: деление в разы медленнее умножения. А при сложении она чаще всего и не нужна.

Если оба слагаемых уже приведены по модулю, их сумма меньше $2m$. Значит, достаточно одного вычитания:

long long add(long long a, long long b) {
    a += b;
    return a >= MOD ? a - MOD : a;
}

Вычитание — симметрично:

long long sub(long long a, long long b) {
    a -= b;
    return a < 0 ? a + MOD : a;
}

Умножение без остатка не обойдётся, но и там % ровно один:

long long mult(long long a, long long b) {
    return a * b % MOD;
}

При $m \approx 10^9$ произведение доходит до $10^{18}$ и в long long помещается. Если аргументы могут быть int, приведение обязательно: 1LL * a * b % MOD.

Зачем функции, а не выражения

Причина не только в скорости. Гораздо важнее вторая.

Когда модуль расставляется вручную, где-то его забывают. И это не абстрактный риск: строка вида

answer = (answer - bad) % MOD;

при answer < bad даёт отрицательное число, которое проверяющая система не примет. Обнаруживается это в самом конце длинного решения, и найти причину тяжело: остальные ответы правильные.

С функцией sub такой ошибки не бывает по построению.

Структура вместо функций

Код с add(mult(h, P), c) читается плохо. Альтернатива — обернуть остаток в тип:

struct Mint {
    long long x = 0;
    Mint() = default;
    Mint(long long v) : x((v % MOD + MOD) % MOD) {}

    Mint operator+(Mint o) const { long long r = x + o.x; return Mint::raw(r >= MOD ? r - MOD : r); }
    Mint operator-(Mint o) const { long long r = x - o.x; return Mint::raw(r < 0 ? r + MOD : r); }
    Mint operator*(Mint o) const { return Mint::raw(x * o.x % MOD); }
    bool operator==(Mint o) const { return x == o.x; }

    static Mint raw(long long v) { Mint m; m.x = v; return m; }
};

Теперь хеш пишется как обычная арифметика:

Mint h = 0;
for (char c : s) h = h * P + (c - 'a' + 1);

Читается как формула, а модуль расставлен везде и всегда.

Отдельный конструктор raw нужен, чтобы не брать остаток от значения, которое уже приведено, — иначе каждая операция стоила бы лишнее деление.

Ловушка с неявным преобразованием

Конструктор Mint(long long) без explicit позволяет писать h * P, где P — обычное число. Это удобно.

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

В случае Mint риск невелик — операции все одного смысла. Но если добавите операторы, у которых есть перегрузки с разными типами, стоит перепроверить.

Когда модуль не влезает

При $m \approx 10^{18}$ произведение выходит за long long. Варианты:

__int128 — самое простое:

long long mult(long long a, long long b) { return (__int128)a * b % MOD; }

Бинарное умножение — если __int128 недоступен. Идея как у быстрого возведения в степень: $a \cdot b = 2a \cdot \frac{b}{2}$ при чётном $b$, и $a \cdot b = a \cdot (b-1) + a$ при нечётном. Удвоение делается сложением, которое не переполняется.

long long binMult(long long a, long long b) {
    long long result = 0;
    while (b > 0) {
        if (b & 1) result = add(result, a);
        a = add(a, a);
        b >>= 1;
    }
    return result;
}

Логарифм вместо константы — заметно медленнее, и на практике почти всегда лучше взять два хеша по маленьким модулям, чем один по большому.