1106A - Lunar New Year and Cross Counting

Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.

Асимптотика O(n²)

Код:49284766

1106B - Lunar New Year and Food Ordering

Заметим, что каждый человек получит либо d_j блюд типа t_j, либо r_tj блюд типа t_j и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.

Асимптотика

Код:49285005

1106C - Lunar New Year and Number Division

Для начала заметим, что в каждой группе должно быть ровно два элемента, так как (a + b)² > a² + b² для положительных a и b

Покажем, что a_i и b_i должны стоять на "противоположных" позициях в отсортированном массиве, так как

То есть нам надо минимизировать третье слагаемое. Теперь такой выбор a_i и b_i следует из транснеравенства (доказательтво).

Асимптотика

Код:49285168

1106D - Lunar New Year and a Wander

Допустим, мы знаем префикс ответа длины i. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером.

Это можно сделать используя bfs с приоритетной очередью.

Асимптотика

Код:49285447

1106E - Lunar New Year and Red Envelopes

Задача решается методом динамического программирования. Обозначим за dp[i][j] минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени i и Алиса уже отвлекла его j раз.

Тогда из dp[i][j] можно перейти в dp[i + 1][j + 1] (если Алиса отвлекает его на i-том ходе) и в dp[d_choice + 1][j], где d_choice — d конверта, который выберет Боб.

Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию w. Тогда мы сможем узнавать выбор Боба на каждой итерации за .

Асимптотика

Код:49285694

1106F - Lunar New Year and a Recursive Sequence

Допустим f_k = x и f_i = x^y_i. По малой теореме Ферма . Значит мы можем считать y_i по модулю p - 1. Найдем y_n с помощью возведения матрицы в степень.

Причем

Тогда

После того, как мы нашли y_n используя бинарное возведение матрицы в степень, нам надо решить

Заметим, что число 3 является первообразным корнем числа 998244353 (степени тройки имеют все возможные остатки по модулю p)

Значит для какого-либо k выполняется

Из этого следует что для такого k верно и а значит и

Найдем k, которое подходит под эти свойства.

Обозначим за inv(i) элемент, обратный i по модулю p.

Число k представимо в виде k = f * d + s, где f > s. Возьмем число f примерно равное и будем перебирать d. Для каждого d необходимо проверить, существует ли подходящее s. Для этого мы предподсчитаем остатки от деления всех степеней от 0 до f - 1 числа 3^y_n на p.

Преобразуем

Теперь чтобы проверить, что для данного d есть подходящее s надо просто посмотреть, был ли у какой-то степени s числа 3^y_n такой остаток от деления на p, и если был, то найти такое s. Тогда k = f * d + s, a .

Если же после всех итераций по d такого k не нашлось, то ответ —  - 1

Код:49321335