15:05 Разбираются задачи контеста по темам лекций: Z-функция, префикс-функция, бор, Ахо—Корасик, суффиксные структуры, палиндромы. Решения в этой части даны идеями и псевдокодом.
19:05 Условие. Даны строки $P$ (образец, длина $m$) и $T$ (текст). Нужно найти все позиции, где $P$ входит в $T$ почти: допускается, что ровно одна буква (на любой позиции образца) не совпадает; вхождение без ошибок тоже подходит.
19:57 Идея. Зафиксируем начало окна $i$ в тексте: тогда известен и его конец $i+m-1$. Если в окне ровно одна неверная буква, то образец делится на три части: общий префикс с $T[i\ldots]$, одна «плохая» буква и общий суффикс с $T[\ldots i+m-1]$. Достаточно знать длины двух кусков.
20:47 Окно $[i,\,i+m-1]$ — почти вхождение тогда и только тогда, когда $\mathrm{pre}_i+\mathrm{suf}_{i+m-1}\ge m-1$: оставшаяся одна буква между кусками как раз и есть допустимая ошибка. 21:42 Лектор выводит индексы на доске и замечает, что в итоговом выражении длина $P$ сокращается.
Z1 = Z-функция(P # T); pre[i] = Z1[m + 1 + i]
Z2 = Z-функция(rev(P) # rev(T)); suf[j] = Z2[m + 1 + (n − 1 − j)]
для i от 0 до n − m:
если pre[i] + suf[i + m − 1] ≥ m − 1: вывести iВремя и память $O(n+m)$. Идею проверили программно на случайных строках над алфавитом из двух букв против прямого сравнения по окнам: расхождений нет.
23:31 Условие. Даны две последовательности неотрицательных чисел $a$ и $b$ одинаковой длины $n$. Нужно найти число пар $(k,x)$ таких, что после циклического сдвига $a$ на $k$ позиций и xor каждого элемента с $x$ получится $b$.
25:32 Ключевое наблюдение. Пусть $a'_i=a_{(i+k)\bmod n}\oplus x$. Тогда xor соседних элементов не меняется: $a'_i\oplus a'_{i+1}=a_{i+k}\oplus a_{i+k+1}$, потому что $x$ входит дважды и уничтожается. Значит, нужное равенство $a'_i=b_i$ для всех $i$ влечёт равенство xor-ов соседних. 29:24 От неизвестного $x$ мы избавились.
30:17 Для фиксированного $k$ возможен только один $x$: из $a'_0=b_0$ получаем $x=a_k\oplus b_0$. Поэтому достаточно перебирать $k$, а равенство всей последовательности равносильно равенству xor-ов соседних плюс выбору $x$ по первому элементу.
32:18 Алгоритм. Строим циклические xor-ы соседних: $c_i=a_i\oplus a_{(i+1)\bmod n}$ для $a$ и $d_i=b_i\oplus b_{(i+1)\bmod n}$ для $b$, $i=0\ldots n-1$ (включая «стык» последнего с первым). Записываем $c$ два раза подряд, чтобы циклический сдвиг стал обычной подстрокой, и ищем все вхождения $d$ в $cc$ с начальной позицией $k\lt n$ (позиция $k=n$ повторяет $k=0$). Для каждого такого $k$ получаем ровно одну пару $(k,\ a_k\oplus b_0)$.
c[i] = a[i] xor a[(i+1) mod n]; d[i] = b[i] xor b[(i+1) mod n]
найти все k из [0, n) такие, что d совпадает с cc[k .. k + n − 1] (Z-функция или КМП)
ответ = число найденных k37:59 Условие. Даны строка $S$ (большая) и $T$ (маленькая). Нужно найти все вхождения $T$ в $S$ с точностью до переименования букв: разные буквы переходят в разные, одинаковые — в одинаковые.
39:15 Идея. Как и в прошлой задаче, ищем инвариант, не зависящий от переименования. Таким инвариантом служит расстояние до следующей такой же буквы: во что бы ни перешла буква, расстояния между соседними одинаковыми не меняются, и именно они задают разбиение позиций на группы одинаковых.
41:07 Строим $S'$ и $T'$: $S'_i=j-i$, где $j\gt i$ — ближайшая позиция с такой же буквой. Считается одним проходом справа налево с запоминанием для каждой буквы последней встреченной позиции.
42:55 Проблема только у позиций, где следующей такой буквы нет. 43:49 В записи лектор предлагает: в $T'$ на таких местах «может быть что угодно», и запустить КМП на $T'\#S'$, пропуская эти позиции при сравнении.
ab и окно aa в $S$. В $T'$ обе позиции — «следующей нет» (джокеры), в окне у первой буквы следующая есть (расстояние 1), и джокер её «принимает», хотя aa не получается из ab переименованием. Поэтому расстояние в окне нужно обрезать: следующая такая же буква, лежащая за концом окна, считается отсутствующей, и «отсутствует» должно совпадать только с «отсутствует». Но обрезка по концу окна зависит от окна и ломает КМП. Проверка на 20 000 случайных пар строк показала, что КМП с джокером даёт неверный ответ в большинстве случаев.prevT[j], prevS[i] — расстояние до предыдущей такой же буквы (0, если нет)
eq(p, k): ((p, если 0 < p ≤ k, иначе 0) == prevT[k]) // p — значение из текста, k — число совпавших символов
fail = префикс-функция образца: для i = 1..m−1: пока k > 0 и не eq(prevT[i], k): k = fail[k]; если eq(prevT[i], k): k++; fail[i+1] = k
проход по S: k = 0; для каждого i: пока k > 0 и (k == m или не eq(prevS[i], k)): k = fail[k]
если eq(prevS[i], k): k++; если k == m: вхождение с позиции i − m + 145:38 Условие. Дан бор $T$ и набор строк. Нужно найти суммарное число вхождений строк набора в строки бора, причём «вхождение» — буквальное: строка встречается как подстрока пути от корня вниз (путь может продолжаться дальше).
46:33 Идея. Для набора строк строим автомат Ахо—Корасик (его бор $T_1$, суффиксные ссылки, автоматные переходы). Затем обходим бор $T$ в глубину как строку, запоминая в каждой вершине $T$ соответствующую вершину автомата — то есть состояние после чтения пути от корня.
48:31 При спуске по ребру с буквой $c$ вершина автомата меняется по автоматному переходу $\delta(s,c)$; состояние родителя хранится в рекурсии, поэтому после возврата вверх оно не теряется. Для каждой вершины автомата заранее считаем $\mathrm{cnt}[v]$ — число терминальных вершин на пути по суффиксным ссылкам до корня: $\mathrm{cnt}[v]=\mathrm{cnt}[\mathrm{link}(v)]+[v\ \text{терминальна}]$. 49:25 Явно дерево суффиксных ссылок строить не нужно. В ответ при посещении каждой вершины $T$ добавляется $\mathrm{cnt}[\text{состояние}]$.
while по суффиксным ссылкам: амортизация («длина текущего состояния растёт на 1 за символ») работает на строке, но не на дереве — размер бора по числу вершин не оценивает сумму длин порождающих строк. Например, «швабра»: миллион букв a вниз и маленькие веточки, на которых обход многократно «прыгает» по ссылкам. Поэтому нужны именно готовые автоматные рёбра: каждый переход за $O(1)$, всего $O(|T_1|\cdot\sigma)$ памяти ($\sigma=26$).построить автомат по набору, посчитать cnt[v]
dfs(u, s): // u — вершина бора T, s — состояние автомата
ans += cnt[s]
для каждого ребра u --c--> w: dfs(w, δ(s, c))
dfs(корень T, корень автомата)51:20 Условие. Дан набор различных строк. Пара $(i,j)$ «подходит», если из $S_i$ последовательными удалениями первого или второго символа можно получить $S_j$. Нужно посчитать число таких пар.
52:08 Структура процесса. Можно считать, что сначала несколько раз удаляют первый символ, а потом несколько раз — второй. Если удалили второй символ, а затем снова первый, то результат тот же, что при удалении сразу большого куска слева: всё удалённое слева «склеивается» (52:58).
54:53 Критерий. Для $i\ne j$ пара подходит тогда и только тогда, когда выполнено одно из двух условий: либо $S_j$ — суффикс $S_i$; либо $S_j$ без первой буквы ($S_j[1{:}]$) — суффикс $S_i$, а первая буква $S_j[0]$ встречается в $S_i$ на позиции строго меньше $|S_i|-|S_j|$ (55:46).
c — суффикс строки cbc, но буква c встречается и раньше); считать такую пару нужно один раз. Критерий проверен программно на всех строках над тремя буквами длины до 8 против перебора достижимых строк.56:37 Работать удобнее с префиксами, поэтому разворачиваем все строки: «суффикс» становится «префиксом», а «буква левее начала суффикса» — «буква правее конца префикса». Теперь пара подходит, если $S_j$ — собственный префикс $S_i$, либо $S_j$ без последней буквы — префикс $S_i$, а последняя буква $S_j$ встречается в $S_i$ правее этого префикса, не считая сразу следующую за ним позицию.
57:35 Строим бор на развёрнутых строках. 1:00:07 Первая мысль — хранить в каждой вершине множество букв из поддерева (маска по 26 буквам, а ещё нужно уметь считать количество). Это слишком тяжело по памяти, и после обсуждения со слушателями (1:02:31) находится экономный способ.
построить бор по развёрнутым строкам; для каждой S_j:
term[вершина(S_j)] = true; mask[вершина(S_j без последней буквы)] |= бит(последняя буква S_j)
для каждой S_i:
cnt[c] = число букв c в S_i; m = маска букв с cnt[c] > 0; v = корень
для L от 0 до |S_i| − 1: // v — вершина, соответствующая префиксу S_i[0..L)
если term[v]: ответ += 1 // S_j — собственный префикс S_i
c = S_i[L]; cnt[c] −= 1; если cnt[c] == 0: m −= бит(c) // теперь m — буквы S_i[L+1..]
ответ += popcount(mask[v] & m & ~бит(c))
v = ребро(v, c)1:19:24 Условие. Дано $2n$ чисел (до $2^{30}$). Алиса и Боб ходят по очереди, начинает Алиса: Алиса берёт число $x$, Боб — число $y$, и записывается число $x\oplus y$. После $n$ раундов смотрим на $n$ записанных чисел и берём максимальное. Алиса хочет его максимизировать, Боб — минимизировать. Нужно найти итог при оптимальной игре.
1:20:13 Лексикографический взгляд. Дополним числа до 30 бит ведущими нулями: тогда сравнение чисел совпадает с лексикографическим сравнением битовых строк, и ответ можно искать жадно по старшим битам.
1:21:13 Берём старший бит $L$ и делим числа на множества $X$ (бит стоит) и $Y$ (бит не стоит). Количества $\mathrm{cnt}_1=|X|$ и $\mathrm{cnt}_0=|Y|$ имеют одну чётность: всего чисел чётное количество.
1:23:00 Случай 1: $\mathrm{cnt}_1$ чётно. Боб разбивает $X$ на пары и $Y$ на пары; на любой ход Алисы отвечает партнёром по паре. Тогда ни один записанный xor не содержит бита $L$, и игра распадается на две независимые игры — на $X$ и на $Y$ (в каждой Алиса ходит первой, Боб отвечает в том же множестве). 1:26:42 Ответ — максимум из ответов этих двух игр.
1:26:42 Случай 2: $\mathrm{cnt}_1$ нечётно. Тогда в любой партии обязательно найдётся раунд, где одно число из $X$, а другое из $Y$: xor этой пары содержит бит $L$, а все остальные раунды (если Боб ведёт себя разумно) бита $L$ не содержат. Значит, значение партии определяется парой «из разных множеств».
1:33:52 Реализация через бор по битам. Кладём все числа в бор (30 уровней). Для вершины $v$ считаем размер поддерева. Если число терминальных в $v$ чётно, ответ — максимум ответов двух детей; если нечётно, считаем минимальный xor между числами из левого и правого поддерева и дальше не спускаемся. Минимальный xor между двумя множествами ищется спуском по бору: для каждого числа из меньшего множества запрос «число с минимальным xor» в боре другого за $O(L)$. 1:39:25 Каждое число участвует в такой операции один раз — на вершине, где происходит остановка, — и поддеревья после остановки не пересекаются, поэтому суммарно $O(nL)$.
solve(v, бит): // v — вершина бора, бит — текущий уровень
если размер(v) чётен:
вернуть max(solve(левый), solve(правый)) // отсутствующий ребёнок даёт 0
иначе:
вернуть min x xor y по x из левого, y из правого поддерева // спуск по бору
ответ = solve(корень, 29)1:40:34 Подсчёт палиндромов. Число подстрок-палиндромов в строке длины $10^5$ считается перебором центра (отдельно для чётной и нечётной длины) с радиусом из алгоритма Манакера либо хэшей с бинарным поиском; Манакер даёт $O(n)$.
1:41:37 Условие (по записи лекции). В строке нужно посчитать число подстрок, которые являются конкатенацией двух подряд идущих палиндромов одинаковой длины. Рассматриваются по отдельности случаи чётной и нечётной длины палиндромов;
1:44:37 Идея. Посчитаем Манакером для каждого центра максимальную длину палиндрома $m_c$ (центры нумеруем по «удвоенной» строке: нечётные палиндромы — чётные номера, чётные — нечётные, расстояние между соседними центрами — полсимвола). Пара подходящих подстрок задаётся двумя центрами $i\lt j$: центры соседних палиндромов длины $\ell$ отстоят на $\ell$ символов, то есть $j-i=2\ell$ в удвоенных координатах. Условия: оба палиндрома длины $\ell$ существуют, то есть $\ell\le m_i$ и $\ell\le m_j$.
1:46:17 Переписываем условия так, чтобы всё, что зависит от одного индекса, оказалось в одной части:
$$ j\le i+2m_i,\qquad i\ge j-2m_j,\qquad i\lt j. $$Кроме того, чётность длины $\ell$ (то есть класс $i\bmod 4$ и $j\bmod 4$) должна быть согласована: для $i$ чётного нужно $j\equiv i+2\pmod 4$, для $i$ нечётного — $j\equiv i\pmod 4$.
1:49:05 Требования вида «часть зависит от $i$, часть — от $j$» перебором не посчитать ($O(n^2)$). 1:50:04 Превращаем в геометрию: каждому $i$ соответствует точка с координатами $(i,\ i+2m_i)$, каждому $j$ — прямоугольник: $x\in[j-2m_j,\ j-1]$, $y\ge j$. Пара подходит, если точка $i$ лежит внутри прямоугольника $j$.
1:51:25 Подсчёт точек в прямоугольниках. Каждый прямоугольник раскладываем на разность двух «квадрантов» (до правого края $x\le j-1$ и до $x\le j-2m_j-1$, оба с условием $y\ge j$). 1:52:13 Сортируем события по $x$ (при равенстве сначала точки, потом запросы), точки добавляем в дерево по $y$ (дерево отрезков или Фенвика), запрос — число точек с $y\ge j$. 1:54:20 Условие согласованности чётности решается тем, что мы запускаем сканлайн отдельно для каждого класса $(i\bmod4,\ j\bmod4)$.
для каждого класса (ci, cj) по модулю 4:
события: точка (x = i, y = i + 2·m[i]) для i ≡ ci;
запрос (x = j − 1, +1) и (x = j − 2·m[j] − 1, −1) со значением y = j для j ≡ cj
сортировка по x, при равных — точки раньше запросов
проход: точка → add(y); запрос → ответ += знак · (число добавленных точек с y ≥ j)Время $O(n\log n)$. 1:43:28 Лектор отдельно разбирает чётные палиндромы и оставляет нечётные «упражнением читателя» (там меняется лишь $\pm1$ в границах); в удвоенной нумерации центров оба случая обрабатываются одним сканлайном.
1:55:07 Все вхождения набора строк в текст. Задача «с лекции»: строим автомат Ахо—Корасик, идём по тексту, а в каждой вершине поднимаемся по сжатым суффиксным ссылкам (ссылкам на ближайшую терминальную вершину) и выводим вхождения. Гарантируется, что вхождений адекватное число, поэтому вывод укладывается во время.
1:55:56 Вирус. Даны $n$ бинарных строк. Нужно определить, существует ли бесконечная бинарная строка, не содержащая ни одной из них. Строим автомат Ахо—Корасик по набору. Если такая бесконечная строка существует, то при чтении её автомат никогда не оказывается в «плохой» вершине. Поэтому: 1:56:46 помечаем плохими все терминальные вершины и все вершины, из которых по суффиксным ссылкам достижима терминальная (в записи это сформулировано как «забанить поддерево терминальных»); оставшиеся вершины и автоматные рёбра между ними образуют ориентированный граф. 1:57:40 Бесконечная строка существует тогда и только тогда, когда в этом графе из корня достижим цикл.
1:58:37 Показанные слова. Есть $n$ строк и $q$ запросов двух видов: «показать слово» (добавить его в список просмотренных) и «спросить про индекс $i$» — сколько из показанных к этому моменту слов входит как подстрока в $S_i$. 2:01:31 Если бы словарь был фиксирован, строился бы автомат по нему и считался проход по $S_i$. Добавлять слова в автомат «на лету» нельзя, поэтому 2:02:34 предлагается взять сразу все слова из запросов и построить автомат по ним, а потом проходить по $S_i$. На этом месте разбор прерывается: 2:03:40 время занятия вышло, лектор передаёт слово следующему преподавателю и объявляет перерыв.
2:06:53 Четыре задачи тура разобраны быстро; подробности лектор обещает в письменном разборе, поэтому здесь даны основные идеи.
2:06:53 Условие (в записи пересказано частично). Есть вертикальные и горизонтальные полосы и много запросов: человека ставят в точку, он идёт вниз со скоростью одна клетка в минуту; направление на перекрёстках зависит от чётности пройденного (2:07:45). Для каждого запроса надо сказать, где он окажется через $T$ минут.
2:07:45 Идея. Пока отрезки чётной длины, направление после них не меняется, а первый нечётный отрезок его меняет. 2:08:38 Поэтому чётные отрезки «сжимаем» до ближайшего нечётного. После сжатия маршрут — змейка: нечётный шаг вниз, нечётный вправо, и так далее.
2:09:28 Для запроса $T$ бинпоиском перебираем число полных ходов $x$: по префиксным суммам проверяем, что $x$ ходов укладываются в $T$, а ещё один уже нет. Остаток времени засчитывается как движение внутри следующего отрезка.
2:11:04 Условие. Есть дек и запросы: добавить число слева или справа, убрать слева или справа. Каждое число добавляется не более 10 раз; числа в каждый момент различны и не превосходят $10^6$. После каждого запроса надо выводить длину самой длинной цепочки $a_{i_1}\mid a_{i_2}\mid\dots$ (каждое следующее делится на предыдущее) 2:11:04 и их число.
2:12:02 Длина ответа мала. Если числа различны, то $a_2\ge 2a_1$, $a_3\ge 2a_2$ и т. д., откуда $a_k\ge 2^{k-1}a_1\ge 2^{k-1}$. При $a_k\le10^6$ получаем $k\le 20$–$22$.
2:13:03 Динамика. $dp[i][\ell]$ — число цепочек длины $\ell$, начинающихся с элемента $i$ (в дек добавляются только справа, а слева — удаляются, поэтому «правые» цепочки меняются только при добавлении/удалении). Поддерживаем максимум длины и число цепочек этой длины.
2:18:34 Лектор отмечает, что в разборе заявлены около $1{,}4\cdot10^8$ операций и 2–3 секунды, поэтому массивы лучше делать статическими, а не векторами.
2:19:22 Условие (по записи — частично). Лампочки стоят на отрезках с шагом $M$, электрики — тоже на отрезке с шагом $M$ от $A$ до $B$; нужно минимизировать время ремонта. Малая подгруппа ($n,p\le8$) решается перебором, следующая — динамикой за $O(n^2s)$.
2:20:18 Динамика. $dp[i][j]$ — минимум времени, чтобы починить первые $i$ лампочек, использовав $j$ рабочих. Каждый рабочий обслуживает подотрезок лампочек: если пути двух рабочих пересеклись, один из маршрутов можно обрезать. Маршрут рабочего — либо «сначала влево до конца, потом вправо», либо наоборот, стоимость $\min(x-l,\ r-x)+(r-l)$ (с поправкой на $\pm1$).
2:22:06 Ускорение. Между двумя соседними лампочками на расстоянии $d$ возможно лишь 5 вариантов: никто не проходит ($0$), один проход вправо ($d$), один влево ($d$), правый разворот: идти вправо и вернуться ($2d$), левый разворот ($2d$). 2:23:59 Состояние — один из пяти вариантов последнего промежутка. Динамика идёт одним линейным проходом, на каждом шаге — $5\times5=25$ переходов с добавкой $0$, $d$ или $2d$.
2:25:46 Переход можно записать как «умножение» вектора из 5 значений на матрицу $5\times5$ в полукольце $(\min,+)$: $C_{ij}=\min_k (A_{ik}+B_{kj})$. 2:26:38 Эта операция ассоциативна (лектор доказательство опускает, оно будет на лекциях дальше), поэтому длинные серии одинаковых переходов считаются бинарным возведением матрицы в степень за $O(\log p)$ матричных умножений по $5^3=125$ операций.
2:28:26 Если все $M=1$ (лампочки подряд), ответ — произведение матриц по отрезкам (степени по длинам). 2:29:22 Если $M\gt1$, прогрессии разных остатков накладываются, поэтому лампочки раскладываем в таблицу «длина × остаток по модулю $M$». 2:31:11 Для подгруппы $n,p\le 10^4$ все нужные расстояния считаются за квадрат плюс логарифм (дерево Фенвика); для полной группы нужна оптимизация, которую лектор оставляет письменному разбору. 2:33:20 Для последних баллов предлагается дерево отрезков, где в вершине хранится произведение матриц.
2:34:17 Условие. Дан шаблон перестановки: часть элементов известна, часть — произвольна. Для перестановки $p$ определим $f(p)=\min_i |p_i-p_{i+1}|$. Перестановка экстремальна, если $f(p)$ максимально среди всех перестановок длины $n$. Нужно посчитать число экстремальных перестановок, подходящих под шаблон.
2:35:08 Чётное $n=2k$. Делим числа на блоки $[1,k]$ и $[k+1,2k]$. Любые два числа из одного блока рядом стоять не могут (разность была бы меньше $k$), поэтому блоки чередуются, и $f=k$. 2:36:04 Числа $k$ и $k+1$ имеют единственного подходящего соседа каждое, значит, стоят на концах, а дальше перестановка задана однозначно «змейкой» с шагом $k$. Экстремальных всего две: сама змейка и её разворот. Для каждой проверяем совпадение с шаблоном. (Программный перебор для $n\le 8$ подтверждает: максимум $f$ равен $n/2$ и достигается ровно на двух перестановках; для нечётных $n\le9$ максимум равен $k=\lfloor n/2\rfloor$.)
2:37:00 Нечётное $n=2k+1$. Блоки $[1,k]$, $\{k+1\}$, $[k+2,2k+1]$. Оценка $f\le k$ та же, и она достигается. Но теперь число $k+1$ мешает: 2:38:40 либо оно стоит с краю, либо во внутренней позиции — тогда его соседи только $1$ и $2k+1$. Различаются случаи «позиция $k+1$ чётная или нечётная».
2:39:30 Числа удобно разбить на пары $(x,\ x+k)$: в экстремальной перестановке пары должны быть соседями (с разностью ровно $k$). Перестановка строится отрезками: 2:42:11 если уже расставлены числа $1..g-1$ внутри отрезка, то числа $1+g$ и $1+g+k$ ставятся однозначно — к краю, где сейчас находится меньшее значение; так отрезок расширяется на 2.
2:54:55 Перебирая позицию числа $k+1$ и считая предпосчитанные биномы, получаем решение за $O(n^2)$ при $n\le 20000$ (2:56:08: порядка $2\cdot10^8$ операций, укладывается в 2 секунды; в худшем случае различных значений не более $n/2$). Подробный разбор лектор обещает в письменном виде.
3:37:04 Тема лекции — «Математика 1». Начинается она с «легендарной» вещи — решета Эратосфена: путь от $O(n\log n)$ через $O(n\log\log n)$ к линейному решету. Весь код ниже — на C++17 (проверен на случайных тестах и перебором).
3:37:58 Заводим массив $\mathrm{lp}$ (наименьший простой делитель), изначально нулевой. Идём $i$ от 2 до $A$: если $\mathrm{lp}[i]=0$, то $i$ простое, кладём $\mathrm{lp}[i]=i$. Затем для каждого $i$ проходим по $j=2i,3i,\dots\le A$ и записываем $\mathrm{lp}[j]=i$ там, где значение ещё не записано. Сколько это работает? Для фиксированного $i$ — $\lfloor A/i\rfloor$ шагов, суммарно $A\cdot(\frac12+\frac13+\dots+\frac1A)$.
3:40:40 Округление можно отбросить. 3:42:23 Оценка сверху: разбиваем слагаемые на группы $\frac1{2^k},\dots,\frac1{2^{k+1}-1}$: в группе $2^k$ слагаемых, каждое не больше $2^{-k}$, значит, сумма группы не больше 1. Групп $\log_2 A$, поэтому $\sum\le\log_2 A$.
3:44:09 Оценка снизу (по площади под графиком): в группе $\frac1{2^k+1},\dots,\frac1{2^{k+1}}$ каждое слагаемое не меньше $2^{-(k+1)}$, сумма группы не меньше $\frac12$, откуда $\sum\ge\frac12\log_2 A$. 3:45:48 Итого $\Theta(\log A)$, и решето работает за $\Theta(A\log A)$.
3:48:15 Внутренний цикл достаточно запускать только для простых $i$ (3:49:15: тогда сумма $\sum_{i\le A,\ i\ \text{простое}}\frac Ai$, а простых до $A$ около $A/\ln A$, и сумма даёт $\ln\ln A$ вместо $\ln A$; подробности — в учебнике). 3:50:07 Ещё ускорение: внутренний цикл начинается не с $2i$, а с $i\cdot i$ (меньшие кратные уже отмечены меньшими простыми). Осторожно: $i\cdot i$ в int переполняется при $i\gtrsim46341$, поэтому считаем в long long.
const int A = 100000;
int lp[A + 1]; // lp[i] — наименьший простой делитель i (0, пока не найден)
void sieve_simple() {
for (int i = 2; i <= A; i++)
if (lp[i] == 0) { // i простое
lp[i] = i;
for (long long j = 1LL * i * i; j <= A; j += i) // i*i считаем в long long: в int будет переполнение
if (lp[j] == 0) lp[j] = i;
}
}3:50:59 Недостаток: составное число отмечается несколько раз. Например, 30 просматривается при $i=2$, при $i=3$ и при $i=5$. Хочется обходить числа так, чтобы каждое составное $c$ получалось ровно один раз.
3:53:00 Ключевая идея. Любое составное $c$ единственным образом записывается как $c=\mathrm{lp}(c)\cdot i$, где $\mathrm{lp}(c)$ — его наименьший простой делитель. Будем перебирать $i$ (а не $c$), и для каждого $i$ пробегать простые $x$ и записывать $\mathrm{lp}[i\cdot x]=x$. Чтобы $x$ действительно был наименьшим простым делителем $i\cdot x$, нужно $x\le\mathrm{lp}(i)$ (3:58:17: «$x$ не больше минимального простого делителя $i$»). Это условие остановки внутреннего цикла.
const int A = 100000;
int lp[A + 1];
vector<int> primes; // найденные простые по возрастанию
void sieve_linear() {
for (int i = 2; i <= A; i++) {
if (lp[i] == 0) { lp[i] = i; primes.push_back(i); }
for (int x : primes) {
if (x > lp[i] || 1LL * i * x > A) break; // нужно x ≤ lp(i), иначе c = i·x получится повторно
lp[i * x] = x; // x — наименьший простой делитель числа i·x
}
}
}3:58:17 Корректность: каждое составное $c$ имеет единственное представление $c=x\cdot i$, $x=\mathrm{lp}(c)$, $i=c/x$; при этом $\mathrm{lp}(i)\ge x$, поэтому цикл по $i$ дойдёт до $x$ и запишет $\mathrm{lp}[c]=x$ ровно один раз. Время $O(A)$, память $O(A)$. Побочно получили $\mathrm{lp}$ для всех чисел.
4:00:52 Задача. Для каждого $i\le A$ получить список его делителей. Перебирать для $i$ делители неэффективно; наоборот, фиксируем делитель $g$ и дописываем его ко всем числам $2g,3g,\dots$, которые он делит. Для $g$ это $\lfloor A/g\rfloor$ операций, суммарно снова гармонический ряд: $O(A\log A)$ (4:01:41: «за два цикла получили список делителей»). Размер ответа тоже $\Theta(A\log A)$.
4:02:37 Определение. Функция $f$, определённая на натуральных числах, мультипликативна, если для любых взаимно простых $m$ и $n$ выполнено $f(mn)=f(m)\,f(n)$ (значение произведения равно произведению значений, но только если числа взаимно просты; $\gcd(m,n)=1$). Все такие функции можно посчитать для всех $n\le A$ за линейное время, используя линейное решето.
4:04:27 Основная теорема арифметики: $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ с различными простыми $p_i$ и $\alpha_i\ge1$. 4:05:20 Делитель числа $n$ имеет вид $p_1^{\beta_1}\cdots p_k^{\beta_k}$ с $0\le\beta_i\le\alpha_i$, и наоборот, любая такая расстановка даёт делитель. Следовательно,
$$ d(n)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1). $$4:06:12 Для взаимно простых $m,n$ в формулу входят независимые наборы простых, поэтому $d(mn)=d(m)d(n)$.
4:07:00 Считаем значение для степени простого $f(p^\alpha)$, а для остальных чисел пользуемся мультипликативностью. В линейном решете для каждого числа запоминаем наименьший простой делитель, его показатель и саму степень $p^\alpha$. 4:07:48 Когда мы умножаем $i$ на простое $x$: если $x\lt \mathrm{lp}(i)$, то $x$ и $i$ взаимно просты и $f(ix)=f(i)f(x)$; если $x=\mathrm{lp}(i)$, то степень наименьшего простого растёт на 1, и значение пересчитываем как $f(\text{остаток без }p^\alpha)\cdot f(p^{\alpha+1})$ — остаток взаимно прост со степенью. 4:08:42 Для $d$: $d(p^\alpha)=\alpha+1$.
4:09:42 Делитель выбирается независимо по каждому простому, поэтому сумма всех делителей раскладывается в произведение скобок:
$$ \sigma(n)=\prod_{i=1}^{k}\bigl(1+p_i+p_i^2+\dots+p_i^{\alpha_i}\bigr). $$4:10:48 Мультипликативность следует из независимости скобок, а значение на степени простого — сумма геометрической прогрессии $\sigma(p^\alpha)=\frac{p^{\alpha+1}-1}{p-1}$.
4:11:36 $\varphi(n)$ — количество чисел от 1 до $n$, взаимно простых с $n$. Например, $\varphi(6)=2$ (числа 1 и 5). Мультипликативность неочевидна, докажем её.
4:14:03 Доказательство. Пусть $\gcd(m,n)=1$. Запишем числа $0,1,\dots,mn-1$ в таблицу $n\times m$ по строкам: в строке $r$ стоят числа $rm,\dots,rm+m-1$: строк $n$, столбцов $m$. Взаимная простота с $mn$ равносильна взаимной простоте и с $n$, и с $m$.
Итого взаимно простых с $mn$ чисел $\varphi(m)\varphi(n)$. В решете значение на степени простого: $\varphi(p^\alpha)=p^{\alpha}-p^{\alpha-1}=p^{\alpha-1}(p-1)$. При умножении на $x=\mathrm{lp}(i)$ получаем $\varphi(ix)=\varphi(i)\cdot x$; при $x\ne\mathrm{lp}(i)$ — $\varphi(ix)=\varphi(i)(x-1)$.
const int A = 100000;
int lp[A + 1];
int e[A + 1]; // e[i] — показатель наименьшего простого в i
int pw[A + 1]; // pw[i] — наибольшая степень наименьшего простого, делящая i (p^e)
int sp[A + 1]; // sp[i] — 1 + p + … + p^e для этого простого (хватает и для A ≤ 1e5)
long long d[A + 1], sigma[A + 1], phi[A + 1];
void mult_sieve() {
vector<int> primes;
d[1] = sigma[1] = phi[1] = 1; pw[1] = 1;
for (int i = 2; i <= A; i++) {
if (lp[i] == 0) { // i простое: значения для p^1
lp[i] = i; primes.push_back(i);
e[i] = 1; pw[i] = i; sp[i] = i + 1;
d[i] = 2; sigma[i] = i + 1; phi[i] = i - 1;
}
for (int x : primes) {
if (x > lp[i] || 1LL * i * x > A) break;
int c = i * x; lp[c] = x;
if (x < lp[i]) { // x не делит i ⇒ gcd(i, x) = 1: умножаем значения
e[c] = 1; pw[c] = x; sp[c] = x + 1;
d[c] = d[i] * 2; sigma[c] = sigma[i] * sp[c]; phi[c] = phi[i] * (x - 1);
} else { // x = lp(i): показатель наименьшего простого вырос на 1
e[c] = e[i] + 1; pw[c] = pw[i] * x; sp[c] = sp[i] * x + 1;
int rest = c / pw[c]; // часть без наименьшего простого: она взаимно проста с p^e
d[c] = d[rest] * (e[c] + 1);
sigma[c] = sigma[rest] * sp[c];
phi[c] = phi[i] * x; // φ(p^k) = p·φ(p^(k−1)) при k ≥ 2
}
}
}
}Все три функции $d,\sigma,\varphi$ проверены для $i\le 20000$ прямым подсчётом по определению, а для остальных $i\le10^5$ — по разложению на простые.
4:20:30 Теорема. Если $\gcd(a,m)=1$, то $a^{\varphi(m)}\equiv1\pmod m$.
Доказательство. 4:21:30 Выпишем все $\varphi(m)$ чисел, взаимно простых с $m$: $x_1,\dots,x_{\varphi(m)}$. Умножим каждое на $a$: числа $ax_i$ тоже взаимно просты с $m$ (произведение взаимно простых взаимно просто). 4:22:24 Они попарно различны по модулю $m$: из $ax_k\equiv ax_t$ при $\gcd(a,m)=1$ следует $x_k\equiv x_t$. Значит, множество остатков $\{ax_i\}$ совпадает с множеством остатков $\{x_i\}$. Перемножая все числа, получаем $a^{\varphi(m)}\prod x_i\equiv\prod x_i$; сокращая взаимно простое с $m$ произведение, получаем $a^{\varphi(m)}\equiv1$.
4:23:21 Следствие: $a^{-1}\equiv a^{\varphi(m)-1}\pmod m$. Для простого модуля $p$ имеем $\varphi(p)=p-1$ (малая теорема Ферма), и обратный находится бинарным возведением в степень. Но для составного большого модуля нужно знать $\varphi(m)$, что требует разложения на простые, — неэффективно.
4:24:21 Напоминание: $\gcd(a,0)=a$, $\gcd(a,b)=\gcd(b,\ a\bmod b)$. Кроме самого НОД, решим диофантово уравнение $ax+by=g$, $g=\gcd(a,b)$ (то есть найдём целые $x,y$).
4:25:43 Все решения. Если $(x,y)$ — решение, то $(x+\frac bg t,\ y-\frac ag t)$ — тоже решение при любом целом $t$. Других нет: для двух решений $(x_1,y_1)$ и $(x_2,y_2)$ имеем $a(x_1-x_2)=b(y_2-y_1)$, то есть $\frac ag(x_1-x_2)=\frac bg(y_2-y_1)$, а так как $\frac ag$ и $\frac bg$ взаимно просты, $\frac bg\mid x_1-x_2$. Достаточно найти одно решение.
4:27:51 Рекурсия. При $b=0$ решение $x=1,\ y=0$. Пусть для пары $(b,\ a\bmod b)$ уже найдено $bx_1+(a\bmod b)y_1=g$. Так как $a\bmod b=a-\lfloor a/b\rfloor b$, подставляем и группируем:
$$ a\,y_1+b\,\bigl(x_1-\lfloor a/b\rfloor\,y_1\bigr)=g, $$откуда $x=y_1$, $y=x_1-\lfloor a/b\rfloor y_1$. Время — как у обычного алгоритма Евклида, $O(\log\min(a,b))$.
4:28:46 Обратный по модулю. Пусть $\gcd(a,m)=1$. Решим $ax+my=1$. Тогда $ax\equiv1\pmod m$, то есть $x\bmod m$ — обратный к $a$. Это работает для любого модуля (не только простого) и без подсчёта $\varphi$.
typedef long long ll;
// возвращает g = gcd(a, b) и числа x, y, для которых a·x + b·y = g
ll egcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) { x = 1; y = 0; return a; }
ll x1, y1;
ll g = egcd(b, a % b, x1, y1); // b·x1 + (a mod b)·y1 = g
x = y1; // a mod b = a − ⌊a/b⌋·b ⇒ подставляем и группируем по a и b
y = x1 - (a / b) * y1;
return g;
}
// обратный к a по модулю m (gcd(a, m) = 1), результат в [0, m)
ll inv(ll a, ll m) {
ll x, y;
egcd(a, m, x, y); // a·x + m·y = 1 ⇒ a·x ≡ 1 (mod m)
return (x % m + m) % m;
}4:30:33 Теорема. Пусть $m_1,\dots,m_n$ попарно взаимно просты, $M=m_1\cdots m_n$. Тогда набор остатков $(a_1,\dots,a_n)$ по этим модулям однозначно соответствует остатку $x\bmod M$: существует ровно одно $x\in[0,M)$ с $x\equiv a_i\pmod{m_i}$ для всех $i$.
4:31:52 Построение. Найдём число $K_i$, которое по модулю $m_i$ даёт 1, а по остальным модулям даёт 0. Для этого возьмём произведение всех остальных модулей $M_i=M/m_i$ (оно делится на все $m_j$, $j\ne i$) и умножим на обратное к нему по модулю $m_i$ (оно существует, так как $\gcd(M_i,m_i)=1$): $K_i=M_i\cdot M_i^{-1}\bmod m_i$. 4:32:55 Тогда $x=\sum a_iK_i\bmod M$.
// попарно взаимно простые модули m[i]; возвращает x mod M, M = ∏ m[i], с x ≡ a[i] (mod m[i])
ll crt(const vector<ll>& a, const vector<ll>& m) {
ll M = 1;
for (ll v : m) M *= v;
ll x = 0;
for (size_t i = 0; i < a.size(); i++) {
ll Mi = M / m[i]; // делится на все модули, кроме m[i]
ll K = Mi * inv(Mi % m[i], m[i]) % M; // K ≡ 1 (mod m[i]), K ≡ 0 (mod остальным)
x = (x + a[i] % M * K) % M;
}
return x;
}4:32:55 Пусть даны множества $M_1,\dots,M_n$. Мощность их объединения:
$$ \Bigl|\bigcup_{i=1}^{n}M_i\Bigr|=\sum_i|M_i|-\sum_{i\lt j}|M_i\cap M_j|+\sum_{i\lt j\lt k}|M_i\cap M_j\cap M_k|-\dots+(-1)^{n+1}|M_1\cap\dots\cap M_n|. $$4:33:44 Идея через подсчёт элементов. Сначала складываем мощности множеств — элемент, лежащий в нескольких, посчитан несколько раз. 4:34:43 Вычитаем попарные пересечения: элементы, лежащие ровно в двух множествах, теперь учтены корректно (дважды минус один раз). 4:35:33 Элемент в ровно трёх множествах: добавлен 3 раза, вычтен 3 раза (по числу пар), значит, нужно добавить тройные пересечения. 4:36:24 Для четырёх: $4-6+4=2$, снова вычитаем четверные, и так далее, пока не дойдём до пересечения всех множеств.
4:37:19 Прямой перебор подмножеств даёт $2^n$ слагаемых, что неудобно; на практике группы пересечений одинакового размера часто учитывают одновременно.
// сколько чисел из [1, N] взаимно просты с n: включения-исключения по простым делителям n
long long coprime_count(long long N, long long n) {
vector<long long> ps;
for (long long p = 2; p * p <= n; p++)
if (n % p == 0) { ps.push_back(p); while (n % p == 0) n /= p; }
if (n > 1) ps.push_back(n);
long long res = 0;
for (int mask = 0; mask < (1 << ps.size()); mask++) { // подмножество простых; 2^k слагаемых, k ≤ 9 для n ≤ 1e9
long long prod = 1; int bits = 0;
for (size_t i = 0; i < ps.size(); i++)
if (mask >> i & 1) { prod *= ps[i]; bits++; }
res += (bits % 2 ? -1 : 1) * (N / prod); // нечётные подмножества вычитаем
}
return res;
}4:37:19 $\binom nk$ — число способов выбрать $k$ объектов из $n$. Свойства (все — комбинаторные доказательства):
4:44:02 В таблице $n\times m$ путей из левого верхнего угла в правый нижний (шаги вправо и вниз) всего $\binom{n+m-2}{n-1}$: из $n+m-2$ шагов выбираем $n-1$ шагов вниз. Соответствие между путями и парами слагаемых — взаимно однозначное (4:44:56).
4:45:58 $\mathrm{Cat}_n$ — количество правильных скобочных последовательностей длины $2n$: открывающая скобка даёт $+1$ к балансу, закрывающая $-1$, баланс всегда неотрицателен и в конце равен 0. Это пути из $(0,0)$ в $(n,n)$ шагами вправо/вниз, не заходящие по одну сторону диагонали (4:46:49: баланс — разность координат).
4:47:49 Всего путей $\binom{2n}{n}$. Плохие пути — касающиеся «запретной» прямой (на единицу за диагональю). Для плохого пути берём первое касание этой прямой и отражаем оставшуюся часть (меняем «вправо» на «вниз» и наоборот). Получим путь, который вместо $(n,n)$ приходит в клетку $(n-1,n+1)$ (4:48:48: «на один шаг вниз больше и на один вправо меньше»).
4:49:44 Обратно: любой путь в $(n-1,n+1)$ обязательно пересекает прямую, и его «хвост» после первого касания можно отразить, получив плохой путь в $(n,n)$. Это взаимно однозначное соответствие, поэтому плохих путей $\binom{2n}{n-1}$ и
$$ \mathrm{Cat}_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac1{n+1}\binom{2n}{n}. $$(Формула проверена полным перебором скобочных последовательностей для $n\le12$.)
4:49:44 Задача. В таблице $n\times m$ нужно посчитать число пар путей (каждый — шагами вправо и вниз), которые не пересекаются. Первый путь идёт из клетки под верхним левым углом в клетку слева от нижнего правого угла, 4:50:56 второй — из клетки справа от верхнего левого угла в клетку над нижним правым.
4:51:54 Сначала считаем все пары путей без ограничения: произведение двух биномиальных коэффициентов. Но часть пар пересекается. 4:52:47 Возьмём пересекающуюся пару, найдём первую общую клетку и обменяем хвосты путей после неё. Получим пару путей, у которых концы поменялись местами: первый путь пришёл в конец второго и наоборот. Обратное преобразование определено тоже, поэтому пересекающихся пар с исходными концами столько же, сколько всех пар с перепутанными концами.
4:53:50 Пар с перепутанными концами считается произведением двух биномов, и ответ:
$$ \text{ответ}=\binom{n+m-4}{n-2}^{2}-\binom{n+m-4}{n-1}\binom{n+m-4}{n-3}. $$4:54:45 Лектор отмечает, что на контесте будет целая задача на эту идею с динамикой сверху и разбором случаев; ключевая идея — отражение/обмен хвостов.
// C[n][k] по треугольнику Паскаля, C[n][k] = C[n−1][k−1] + C[n−1][k]
const int NMAX = 31;
long long C[2 * NMAX + 1][2 * NMAX + 1];
void build_binom() {
for (int n = 0; n <= 2 * NMAX; n++) {
C[n][0] = 1;
for (int k = 1; k <= n; k++) C[n][k] = C[n - 1][k - 1] + (k <= n - 1 ? C[n - 1][k] : 0);
}
}
long long catalan(int n) { return C[2 * n][n] - (n ? C[2 * n][n - 1] : 0); } // = C(2n, n)/(n+1)
// непересекающиеся пары путей в таблице n×m (старты и финиши — как на рисунке), n, m ≥ 2
long long disjoint_pairs(int n, int m) {
return C[n + m - 4][n - 2] * C[n + m - 4][n - 2] - C[n + m - 4][n - 1] * (n >= 3 ? C[n + m - 4][n - 3] : 0);
}4:55:41 Задача. Распределить $m$ одинаковых шаров по $n$ ящикам (в ящике может оказаться любое число шаров, в том числе 0). Сколько способов?
4:56:40 Поставим шары в ряд и разделим $n-1$ перегородкой на $n$ групп: группа между соседними перегородками — содержимое ящика. Всего в ряду $n+m-1$ объектов; осталось выбрать, на каких $m$ местах стоят шары (остальные места занимают перегородки):
$$ \binom{n+m-1}{m}. $$Формула проверена перебором распределений для $n\le6$, $m\le6$.
4:57:49 Задача (с регионального этапа). Сложили два числа «в столбик» и записали результат. Выражение разрезали на отдельные столбики (две цифры слагаемых и цифра суммы) и перемешали. Нужно найти число способов расставить столбики обратно так, чтобы выражение стало верным.
4:59:00 Столбик характеризуется двумя признаками: требует ли переноса от предыдущего разряда и даёт ли перенос в следующий. Это четыре типа столбиков; если цифры в столбике не могут дать нужную сумму ни при каком переносе, расстановки нет вообще. Столбик, который требует переноса, должен стоять после столбика, дающего перенос; не требующий — после не дающего. 4:59:52 Здесь запись заканчивается (VK ограничивает длительность записи пятью часами), и продолжение разбора — классификация столбиков и подсчёт расстановок — в ней отсутствует.