0:10 Хэш-функция — функция $h$ из какого-то (большого) множества объектов в множество «хэшей» $\{0,1,\dots,M-1\}$. Объекты могут быть любыми: числа, строки, деревья, множества. От хорошей хэш-функции ждут:
3:40 Хэш нужен, чтобы «тяжёлые» объекты кодировать удобными числами (пример из жизни — SHA-256: файл → строка из 256 бит). Объектов намного больше, чем хэшей, поэтому разные объекты могут получить одинаковый хэш — это коллизия. Но если $a=b$, то $h(a)=h(b)$ обязательно. Поэтому: разные хэши ⇒ объекты точно различны; одинаковые хэши ⇒ вероятно равны, но гарантии нет.
6:24 Выберем модуль $M$ (обычно простое число порядка $10^9$) и основание $p$, большее размера алфавита. Каждому символу сопоставим натуральное число (нулевое не подходит: иначе строки «a» и «aa» могли бы совпасть) — например, номер буквы от $1$. Определим
7:44 По сути это запись числа в системе счисления с основанием $p$ (цифры меньше $p$, поэтому алфавит должен быть меньше $p$). Можно писать и по убыванию степеней (схема Горнера $h\leftarrow h\cdot p+s_i$); здесь выбран порядок по возрастанию — потом будет видно, чем он удобен.
13:12 Обычно считают префиксные хэши: $H_{i+1}=H_i+s_i\,p^i$ (или по схеме Горнера). Тогда хэш подстроки $[l,r)$ получается разностью, как в префиксных суммах. Проблема: при вычитании остаётся сумма $\sum_{i=l}^{r-1}s_ip^{i}$, в которой первый символ умножен на $p^l$, а не на $p^0$. Чтобы сравнить две равные подстроки в разных местах, приводим хэши к общей степени: например, домножаем на $p^{N-r}$, чтобы последний символ всегда имел степень $p^{N-1}$ (где $N$ — максимальная длина). Тогда хэши равных подстрок совпадают.
// h[i] — хэш префикса длины i (по возрастанию степеней), pw[i] = p^i mod M
ll get(int l, int r) { // хэш s[l..r), приведённый к степеням p^{N-(r-l)} ... p^{N-1}
ll x = (h[r] - h[l] + M) % M; // sum_{i=l}^{r-1} s_i * p^i
return x * pw[N - r] % M; // домножили: последний символ стоит на p^{N-1}
}
// равенство подстрок [l1,r1) и [l2,r2): длины равны && get(l1,r1) == get(l2,r2)(a - b + M) % M — отрицательный остаток в C++ остаётся отрицательным.pw за $O(n)$; тогда запрос — $O(1)$.16:38 Пример применения: строка длины $n\sim10^5$ и $q\sim10^5$ запросов «равны ли подстроки $[l_1,r_1)$ и $[l_2,r_2)$» — предпосчёт префиксных хэшей за $O(n)$ и ответ на запрос за $O(1)$.
18:44 Число различных подстрок длины $k$: перебрать все подстроки длины $k$, взять хэши и положить в set — размер множества равен числу различных хэшей (коллизии возможны, но редки).
21:29 Коллизии случаются, когда объектов (и хэшей) слишком много: при $10^9+7$ вариантах хэша уже порядка $\sqrt{10^9}$ строк дают коллизию с большой вероятностью (см. «парадокс дней рождения» ниже). Чтобы увеличить пространство хэшей, считают два хэша по разным модулям $M_1,M_2$ (например, $10^9+7$ и $10^9+9$) и сравнивают пары. По китайской теореме об остатках пара остатков по взаимно простым модулям однозначно определяет остаток по модулю $M_1M_2\approx10^{18}$, то есть пространство хэшей возводится «в квадрат», а вычисления остаются в $32$-битных типах (произведения — в 64-битных).
27:29 map — бинарное дерево поиска: операции за $O(\log n)$. Хэш-таблица быстрее: ключу сопоставляется хэш $h(k)$, и пара $(k,v)$ кладётся в ячейку массива с номером $h(k)\bmod N$ ($N$ — размер массива). Две проблемы: массив меньше числа ключей, и на одну ячейку претендуют несколько ключей. Два способа решения.
30:56 В каждой ячейке хранится список пар, получивших этот хэш. get: считаем хэш и просматриваем список ячейки в поисках нужного ключа. Скорость определяется коэффициентом загрузки (load factor) $\alpha=m/N$, где $m$ — число элементов. Пока $\alpha$ ограничено константой, а хэш-функция «случайна», средний список короткий и операции работают за $O(1)$ в среднем. Как у vector: как только $\alpha$ превысит порог (например, $1$), размер массива удваивается и все элементы вставляются заново (хэш по модулю размера изменился); амортизированно это $O(1)$.
41:13 Храним пары прямо в массиве. При вставке считаем $h(k)$; если ячейка занята, пробуем $h(k)+1$, $h(k)+2,\dots$ (по циклу), пока не найдём свободную. get: идём так же, пока не найдём свой ключ или пустую ячейку (тогда ключа нет). Удаление: нельзя просто очистить ячейку (цепочка оборвётся), поэтому ячейку помечают «удалена» (tombstone, «надгробие»). При заполнении (практически — по порогу загрузки, например $1/2$) таблицу перестраивают с удвоением.
unordered_set, unordered_map (и мультиварианты) — закрытая адресация со связными списками; multimap допускает несколько значений на ключ и не имеет operator[].gp_hash_table (открытая адресация, часто в разы быстрее unordered_map, иногда до $10\times$) и cc_hash_table (закрытая, чуть быстрее стандартной), в <ext/pb_ds/assoc_container.hpp> с интерфейсом как у map.map, а если не успевает — gp_hash_table.int упакуйте её в long long: $(a\ll32)+b$.multiset::erase(key) удаляет все вхождения — частый источник ошибок.int, а размеры таблицы — заранее зашитые простые числа, растущие примерно в $2\times$. Поэтому «ломающий» тест — ключи вида $k+i\cdot P$, где $P$ — текущий размер таблицы: все они попадают в одну ячейку, и каждая операция работает за $O(n)$ (суммарно $O(n^2)$). В gp_hash_table размер — степень двойки, и взломать ещё проще.x ^ random_value или splitmix64 со случайной «солью», выбираемой при запуске.64:12 Префиксные суммы на матрице: $pref_{i,j}=pref_{i-1,j}+pref_{i,j-1}-pref_{i-1,j-1}+a_{i,j}$; сумма на прямоугольнике $[l_x,r_x]\times[l_y,r_y]$ равна $pref_{r_x,r_y}-pref_{l_x-1,r_y}-pref_{r_x,l_y-1}+pref_{l_x-1,l_y-1}$ (кусок, вычтенный дважды, возвращаем).
67:38 Хэши работают не только для строк: массивы чисел (до $10^9$ при подходящем $p$) и подматрицы тоже можно хэшировать. Нумеруем элементы матрицы построчно «как одну длинную строку», берём префиксные хэши и для каждой подматрицы приводим их к степени, фиксированной для угла (домножаем на нужную степень $p$ в зависимости от позиции).
71:13 Если в группе $x\gtrsim\sqrt{365}$ человек (в действительности порядка 23), вероятность, что у каких-то двоих совпадают дни рождения, больше $50\%$. Объяснение: пар людей около $x^2/2$. Для хэшей: если возможных хэшей $M$ и объектов около $\sqrt M$, то коллизия уже вероятна. В реальном решении объектов $N^2/2$ подстрок одной строки длины $N=10^5$ — их больше, чем $10^9+7$ хэшей, так что коллизии неизбежны!
75:18 Исправление: перед сравнением хэшей сравнивайте длины подстрок. Подстроки разной длины неравны автоматически, а внутри одной длины $k$ их всего $n$ (а не $n^2$) — вероятность коллизии нормальная. Если объектов всё-таки слишком много — используйте двойной модуль.
79:16 Если везде писать % mod вручную, легко забыть его и долго отлаживаться. Заводим структуру, инвариант которой: значение уже взято по модулю; операции переопределяем.
const int MOD = 1000000007;
struct Hash {
int x; // 0 <= x < MOD
Hash() : x(0) {}
Hash(int v) : x(v) {}
Hash operator+(const Hash &o) const { int r = x + o.x; if (r >= MOD) r -= MOD; return Hash(r); }
Hash operator-(const Hash &o) const { int r = x - o.x; if (r < 0) r += MOD; return Hash(r); }
Hash operator*(const Hash &o) const { return Hash((long long)x * o.x % MOD); } // 1LL — иначе переполнение int
bool operator==(const Hash &o) const { return x == o.x; }
};const (иначе часть выражений не скомпилируется).%: сумма двух значений, меньших MOD, не превосходит $2\,MOD-2$ — хватает одного вычитания; операция % в сотни раз дороже сложения.+=, -=, *= по умолчанию не определены — при желании добавляйте.// хэш строки и префиксные хэши
Hash p(123);
vector<Hash> h(n + 1);
for (int i = 0; i < n; ++i) h[i + 1] = h[i] * p + Hash(s[i] - 'a' + 1); // схема ГорнераПри схеме Горнера хэш подстроки $[l,r)$ получают как h[r] - h[l] * pw[r - l] (где pw[i] — $p^i$): префикс «сдвигается» и вычитается. Хэши равных подстрок тогда совпадают без дополнительного приведения степеней — это самый удобный вариант на практике.
92:51 Если в структуру добавить второе число unsigned long long y и просто складывать/вычитать/умножать его без %, то оно автоматически берётся по модулю $2^{64}$ (переполнение беззнаковых типов определено). Получаем двойной хэш по модулям $M$ и $2^{64}$ почти бесплатно.
using ull = unsigned long long;
struct Hash {
int x; ull y;
Hash() : x(0), y(0) {}
Hash(int a, ull b) : x(a), y(b) {}
Hash operator+(const Hash &o) const { int r = x + o.x; if (r >= MOD) r -= MOD; return Hash(r, y + o.y); }
Hash operator-(const Hash &o) const { int r = x - o.x; if (r < 0) r += MOD; return Hash(r, y - o.y); }
Hash operator*(const Hash &o) const { return Hash((long long)x * o.x % MOD, y * o.y); }
bool operator==(const Hash &o) const { return x == o.x && y == o.y; }
};100:22 Нужно поддерживать множество чисел с операциями «добавить $x$», «удалить $x$» и быстрой проверкой «равны ли два множества». Хэшировать как строку неудобно (нужен порядок). Идея: каждому элементу $x$ сопоставим случайное число $f(x)$ (один раз выбранное, например в map) и положим
103:51 Добавление и удаление — одна операция: h ^= f(x) (xor коммутативен, $a\oplus a=0$). Множества равны ⇒ равны хэши; обратное — с большой вероятностью. Пустому множеству соответствует $0$.
mt19937_64 rng(seed);
map<int, unsigned long long> f;
unsigned long long h = 0; // хэш пустого множества
void toggle(int x) { // добавить или удалить x
if (!f.count(x)) f[x] = rng(); // случайное число для элемента
h ^= f[x];
}109:59 Дубликаты (мультимножества): xor «аннулирует» повторы, поэтому для мультимножеств лучше сумма $h=\sum f(x_i)$ (добавление — «+», удаление — «−») или $h=\sum p^{x_i}\bmod M$ для случайного $p$. Суммы и степени могут переполняться — берите по модулю. Для множеств без повторов обычно достаточно xor.
mt19937 rng(seed); — генератор (mt19937_64 — 64-битный); rng() выдаёт случайное число. Нужно #include <random>.seed (или с постоянным) последовательность при каждом запуске одинакова — удобно для отладки; для защиты от взлома и в стресс-тестировании нужен «плавающий» сид, например chrono::steady_clock::now().time_since_epoch().count() (точность часов важна, если программу перезапускать очень часто).random_device на некоторых платформах и компиляторах возвращает одно и то же — ненадёжен.122:56 Два корневых дерева изоморфны, если вершины одного можно перенумеровать так, чтобы получилось другое (корень в корень, рёбра в рёбра): картинки совпадают с точностью до имён вершин. Научимся проверять это детерминированно (без коллизий).
125:37 Каждой вершине присвоим целое число (хэш): листьям — $0$. Для остальных смотрим на мультимножество хэшей детей (порядок детей неважен, поэтому список сортируем). Если такого набора ещё не было — присваиваем ему следующее по счёту число; если был — то же, что прежде. Тогда поддеревья изоморфны ⇔ хэши равны.
map<vector<int>, int> used; // набор хэшей детей -> номер
vector<int> H(n);
void dfs(int v, int p) {
vector<int> children;
for (int to : g[v]) {
if (to == p) continue;
dfs(to, v);
children.push_back(H[to]);
}
sort(children.begin(), children.end());
if (!used.count(children)) {
int id = used.size(); // следующий свободный номер
used[children] = id;
}
H[v] = used[children];
}
// для сравнения двух корневых деревьев: dfs(root1), dfs(root2) с ОДНИМ и тем же used; сравнить H[root1], H[root2]map.map общий для обоих деревьев.144:08 Если считать хэш только по модулю $2^{64}$ (т. е. через переполнение), то найдётся тест, ломающий любое основание. Строим последовательность: $s_0=\texttt{a}$, $t_0=\texttt{b}$, $s_{k+1}=s_kt_k$, $t_{k+1}=t_ks_k$. Для любого основания $p$ хэши $s_k$ и $t_k$ при достаточно большом $k$ совпадают по модулю $2^{64}$ (разность хэшей содержит произведение множителей, каждый из которых чётный, поэтому делится на высокую степень двойки). Длины порядка $2^{11}$ уже достаточно. Поэтому автор любой задачи, где возможны хэши, почти наверняка добавит такой тест; хэш только по $2^{64}$ использовать нельзя. В паре с простым модулем — можно.
146:11 Для известной пары $(p,M)$ хэш ломается просто: генерируем случайные строки (длиной около $100$), для каждой считаем хэш и кладём в map «хэш → строка»; как только встретился уже имеющийся хэш у другой строки — найдена коллизия. По парадоксу дней рождения хватит порядка $\sqrt M$ итераций (для $M\sim10^9$ это порядка $10^5$).
mt19937 rng(...);
map<long long, string> seen;
while (true) {
string s = randomString(100); // случайная строка из 100 символов
long long h = hashOf(s);
if (seen.count(h) && seen[h] != s) { /* коллизия: seen[h] и s */ break; }
seen[h] = s;
}rng() % MOD, лучше больше алфавита) при каждом запуске: тогда взломщику не известно $p$ и подобрать тест нельзя. Есть и более продвинутые атаки (статьи на Codeforces), но случайное $p$ защищает от базовых.157:12 Дано дерево; у каждой вершины есть цена; нужно поставить в некоторых вершинах фонари минимальной суммарной стоимости так, чтобы каждое ребро было освещено (хотя бы один его конец отмечен) — минимальное по стоимости вершинное покрытие. В общем графе задача NP-трудная, на дереве решается динамикой: $dp_{v,1}$ — минимальная цена для поддерева $v$, если $v$ отмечена; $dp_{v,0}$ — если не отмечена (тогда все дети обязаны быть отмечены).
163:23 Восстановление ответа: либо запоминаем, где какой вариант выбран, либо при обратном спуске выбираем меньшее значение по тем же формулам.
167:08 Нужны два пути без общих вершин, чтобы произведение длин (в рёбрах) было наибольшим. Утверждение: между двумя такими путями есть ребро, при удалении которого дерево распадается на две части, и в каждой части берётся диаметр. Значит, перебираем ребро и перемножаем диаметры двух частей; требуется быстро считать диаметры «поддерева» и «всего дерева без поддерева». Для этого нужны три величины: down[v] — длина самой длинной цепочки вниз от $v$; diam[v] — диаметр поддерева $v$ (максимум из диаметров детей и суммы двух самых длинных цепочек вниз через $v$); up[c] — длина самой длинной цепи, начинающейся ребром в предка (идти вверх или вверх и потом вниз в другую ветвь, для чего хранят второй максимум), и диаметр дерева без поддерева $c$ (комбинация диаметра выше, «вверх+вниз» и диаметров остальных детей).
181:47 Дан неориентированный граф и числа $c_v$ — требуемое число достижимых из $v$ вершин (включая $v$). Если ребро ориентировано $a\to b$, то $c_a\ge c_b$ (из $a$ достижимо всё, что из $b$), причём равенство возможно, только если $a$ и $b$ в одной компоненте сильной связности. Поэтому: если $c_a>c_b$ — ребро ориентируем $a\to b$; если $c_a=c_b$ — вершины должны оказаться в одной сильно связной компоненте, и рёбра внутри такой компоненты нужно ориентировать так, чтобы она стала сильно связной. Это возможно, если в ней нет мостов (теорема Роббинса): запускаем DFS, древесные рёбра ориентируем вниз, обратные — вверх.
188:19 Дана таблица $n\times m$; нужно заменить числа на натуральные так, чтобы в каждой строке и каждом столбце сохранились отношения («меньше», «равно», «больше») между элементами, а максимальное число было минимальным. Равные элементы в строке/столбце объединяем в группы (СНМ). Затем в каждой строке и столбце сортируем группы по значению и проводим ребро «меньше» между соседними по порядку группами — достаточно только соседних, остальные следуют транзитивно. Получаем ориентированный ациклический граф групп; минимальная раскраска — длина самого длинного пути (ранг вершины в слоях): вершины без входящих рёбер получают $1$, затем удаляем их и повторяем. Время $O(nm\log(nm))$.
192:20 Даны пары $(x_i,y_i)$, означающие $p_{x_i}>p_{y_i}$; ищем наименьшее число первых $k$ пар, по которым перестановка восстанавливается однозначно. Пары — рёбра графа; перестановка однозначна, только если топологический порядок единственный, а это — когда между каждыми двумя соседними вершинами порядка есть ребро (иначе соседей можно поменять местами). Каждое из $n-1$ нужных рёбер появилось на шаге $k_j$; ответ — максимум этих $k_j$.
198:38 Нужно выбрать простой путь, а оставшиеся вершины раскрасить в $0/1$ так, чтобы между цветами не было рёбер и число нулей равнялось числу единиц (после удаления пути вершины разбиваются на компоненты связности, каждая красится целиком). Идея: строим путь вдоль DFS-дерева (все не-древесные рёбра идут к предкам). Поддерживаем множества $A,B$ и инвариант: разность размеров $D$ не больше размера текущего поддерева. На каждом шаге берём ребёнка с наибольшим поддеревом $S_1$ как «продолжение пути», а остальные поддеревья раздаём в меньшую часть; если после этого разность равна $S_1$, то отдаём $S_1$ в меньшую часть и закончили; иначе разность меньше $S_1$ и можно спуститься в этого ребёнка с сохранением инварианта.
215:30 Дерево; удалить минимальное число рёбер так, чтобы появилась компонента размера $K$. Динамика на дереве: $dp_{v,k}$ — минимальное число удалённых рёбер в поддереве $v$, чтобы компонента, содержащая $v$, имела размер $k$. Детей присоединяем по одному: либо отрезаем ребро (прибавляем $1$ ко всем значениям), либо оставляем и «склеиваем» размеры, перебирая $(a,b)$ — $dp'_{a+b}=\min(dp_a+dp_{c,b})$. Каждая пара вершин рассматривается один раз, поэтому суммарно $O(n^2)$. Ответ — минимум по $v$ значений $dp_{v,K}$ (плюс $1$, если $v$ не корень, на отрезание ребра к предку).
223:14 Задачи A и B — прямое вычисление. Z-функция $z_i$ — длина наибольшего общего префикса строки и её суффикса с позиции $i$: поддерживаем «самый правый» отрезок $[l,r)$, совпадающий с префиксом; для позиции $i<r$ берём $z_{i-l}$, обрезав по $r-i$, и достраиваем. Префикс-функция $\pi_i$ — длина наибольшего собственного префикса подстроки $[0,i]$, являющегося её суффиксом: идём от $\pi_{i-1}$, пока следующий символ не совпал, откатываясь по $k\leftarrow\pi_{k-1}$.
vector<int> zfunc(const string &s) {
int n = s.size(); vector<int> z(n); z[0] = n;
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i < r) z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) { l = i; r = i + z[i]; }
}
return z;
}
vector<int> pfunc(const string &s) {
int n = s.size(); vector<int> p(n);
for (int i = 1; i < n; ++i) {
int k = p[i - 1];
while (k > 0 && s[i] != s[k]) k = p[k - 1];
if (s[i] == s[k]) k++;
p[i] = k;
}
return p;
}224:38 Строим префикс-функцию для строки pattern + '#' + text (разделитель не встречается в тексте). Позиции $i$, где $\pi_i=|pattern|$, — концы вхождений; начало вхождения $i-2|pattern|$ (с учётом разделителя).
227:22 Нужно понять, на сколько надо сдвинуть вправо строку $s$, чтобы получить $t$. Любой циклический сдвиг $s$ — подстрока длины $n$ в удвоенной строке $ss$. Значит, ищем $t$ в $s+s$ (префикс-функция по t#ss); смещение вхождения определяет сдвиг.
230:51 Нужно для каждой позиции $i$ найти максимальную длину $l\le i+1$, при которой $s_j=s_{i-j}$ при $j<l$ (то есть префикс совпадает с перевёрнутым суффиксом подстроки $[0,i]$). Идея: сравниваем $s$ слева направо с перевёрнутой $s$, а это снова Z-функция, но уже на конкатенации $s+\texttt{\#}+\operatorname{rev}(s)$: для позиции $i$ в перевёрнутой строке (она начинается на позиции $n-1-i$) значение $z$ даёт длину совпадения, которую нужно ограничить $i+1$.
string r(s.rbegin(), s.rend());
auto z = zfunc(s + "#" + r);
for (int i = 0; i < n; ++i)
f[i] = min(z[n + 1 + (n - 1 - i)], i + 1);235:42 Запросы: добавить $x$, удалить $x$, найти $\max_{x\in S}(x\oplus y)$. Сравнение чисел — это сравнение строк из битов от старших к младшим, поэтому жадно идём по битовому бору: на каждом шаге стараемся перейти в бит, противоположный биту $y$ (там $1$ в xor), если такое поддерево непусто. Для удаления в каждой вершине храним число терминальных вершин в поддереве (счётчик); пустые поддеревья не удаляем из памяти, а просто не заходим в них (счётчик $0$).
// бор по 31 биту, cnt[v] — число чисел в поддереве
int query(int y) {
int u = 0, res = 0;
for (int b = 30; b >= 0; --b) {
int bit = (y >> b) & 1, want = bit ^ 1;
int nx = to[u][want];
if (nx != -1 && cnt[nx] > 0) { res |= 1 << b; u = nx; } // можно получить 1 в этом бите xor
else u = to[u][bit];
}
return res;
}245:28 Дана строка длины $n$ (квадратичные решения допустимы). Нужно посчитать число пар подстрок одинаковой длины, из которых одна меньше другой (то есть пар различных подстрок, заданных границами). Упростим: пусть $\alpha$ — префикс; подстрока $\beta$ начинается в позиции $i$ и той же длины. Они совпадают, пока длина $\le z_i$; различны для длин от $z_i+1$ до $n-i$. Значит, пар $(\text{префикс},\ \beta)$ с началом $\beta$ в $i$ равно $n-i-z_i$. Чтобы получить все пары, будем по очереди отбрасывать первый символ (рассматриваем все суффиксы) и для каждого суффикса суммируем $(m-i)-z_i$ по $i\ge1$, где $m$ — длина суффикса. Итого $O(n^2)$.
251:32 Запросы: добавить строку; найти $k$-ю по порядку (лексикографически) строку множества. Кладём строки в бор, в каждой вершине храним число терминальных вершин в поддереве. Спуск: перебираем переходы по возрастанию букв; если в поддереве по этому переходу терминалов $x\le k$ (нумерация с нуля: $x\le k$ означает, что $k$-й там нет), вычитаем $x$ из $k$ и идём дальше; иначе переходим в эту вершину и запоминаем символ. Терминал самой вершины (строка заканчивается здесь) учитывается раньше детей.
257:00 Нужно понять, входит ли массив $B$ в массив $A$ с точностью до прибавления одной константы ко всем элементам $B$. Переходим к массивам разностей соседних элементов: $a'_i=a_i-a_{i-1}$, $b'_i=b_i-b_{i-1}$ — константа сокращается. Первый элемент $b$ не несёт информации; осталось найти $b'_{1..m-1}$ в $a'$ обычным поиском (префикс-функция по массиву чисел).
259:52 Задачи L и M (по словам преподавателей) — «простые» упражнения на префикс-функцию с экономией памяти (онлайн-вычисление без хранения всего массива) и стандартные приёмы, поэтому в записи не разбирались.