Двойное хеширование строк: зачем два модуля и как это снижает шанс коллизии?

При q сравнениях по парадоксу дней рождения вероятность хотя бы одной коллизии примерно q^2 / (2M). Для M ≈ 10^9 и q ≈ 2·10^5 это уже порядка нескольких процентов — отсюда плавающий WA.

Двойное хеширование: считаем пару (h1 mod M1, h2 mod M2) с разными модулями. Две разные строки совпадут по паре только если совпали по обоим — вероятность перемножается и становится ~ q^2 / (M1·M2) ≈ q^2 / 10^18, что практически ноль.

struct Hash2 {
    long long h1, h2;
    bool operator==(const Hash2& o) const { return h1 == o.h1 && h2 == o.h2; }
};
// храните два независимых массива префиксных хешей с (base1,M1) и (base2,M2)

Альтернатива двойному хешу — один модуль 2^61-1: он сам по себе даёт q^2 / 2^61, чего хватает почти всегда, и при этом один проход вместо двух. На олимпиаде я беру 2^61-1 со случайной базой по умолчанию, а двойной хеш — если по какой-то причине нужны 32/64-битные модули и __int128 под рукой нет.

Сложность не меняется: O(n) препроцессинг, O(1) сравнение (с удвоенной константой).