[problem:1106A]↵
------------------↵
↵
Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.↵
↵
Асимптотика $O(n ^ 2)$↵
↵
Код:[submission:49284766]↵
↵
[problem:1106B]↵
------------------↵
↵
Заметим, что каждый человек получит либо $d_{j}$ блюд типа $t_{j}$, либо $r_{t_{j}}$ блюд типа $t_{j}$ и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.↵
↵
Асимптотика $O((n + m)\log{}n)$↵
↵
Код:[submission:49285005]↵
↵
[problem:1106C]↵
------------------↵
↵
Для начала заметим, что в каждой группе должно быть ровно два элемента, так как $(a + b) ^ 2 > a ^ 2 + b ^ 2$ для положительных $a$ и $b$↵
↵
Покажем, что $a_{i}$ и $b_{i}$ должны стоять на "противоположных" позициях в отсортированном массиве, так как↵
↵
$\sum_{i = 1}^{n / 2} (a_{i} + b_{j})^2 = \sum_{i = 1}^{n / 2} a_{i}^2 + \sum_{i = 1}^{n / 2} b_{j}^2 + \sum_{i = 1}^{n / 2}\sum_{j = 1} ^ {n / 2} a_{i} * b_{j}$↵
↵
То есть нам надо минимизировать третье слагаемое. Теперь такой выбор $a_{i}$ и $b_{i}$ следует из транснеравенства ([доказательтво](https://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/55_nerav3_lect.pdf)).↵
↵
Асимптотика $O(n\log{}n)$↵
↵
Код:[submission:49285168]↵
↵
[problem:1106D]↵
------------------↵
↵
Допустим, мы знаем префикс ответа длины $i$. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером. ↵
↵
Это можно сделать используя bfs с приоритетной очередью.↵
↵
Асимптотика $O(n\log{}n + m)$↵
↵
Код:[submission:49285447]↵
↵
↵
[problem:1106E]↵
------------------↵
↵
Задача решается методом динамического программирования. Обозначим за $dp[i][j]$ минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени $i$ и Алиса уже отвлекла его $j$ раз.↵
↵
Тогда из $dp[i][j]$ можно перейти в $dp[i + 1][j + 1]$ (если Алиса отвлекает его на $i$-том ходе) и в $dp[d_choice + 1][j]$, где $d_{choice}$ — $d$ конверта, который выберет Боб.↵
↵
Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию $w$. Тогда мы сможем узнавать выбор Боба на каждой итерации за $O(\log{}n)$.↵
↵
Асимптотика $O(n\log{}k + n * m)$↵
↵
Код:[submission:49285694]↵
↵
[problem:1106F]↵
------------------↵
↵
Допустим $f_{k} = x$ и $f_{i} = x^{y_{i}}$. По малой теореме Ферма $a^b\equiv (a^{b\mod{p - 1}})\mod{p}$. Значит мы можем считать $y_{i}$ по модулю $p - 1$. Найдем $y_{n}$ с помощью возведения матрицы в степень.↵
↵
$\relax y_{i} = (b_{1} * y_{i - 1} + b_{2} * y_{i - 2} + \ldots + b_{k} * y_{i - k})\mod{p - 1}$↵
↵
Причем $\relax y_{1} = 0, y_{2} = 0, \dots, y_{k - 1} = 0, y_{k} = 1$↵
↵
$\begin{pmatrix} y_{i} \\ y_{i - 1} \\ \vdots \\ y_{i - k + 1} \end{pmatrix} = \begin{pmatrix} b_{1} & b_{2} & b_{3} & \dots & b_{k - 1}& b_{k} \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \end{pmatrix} * \begin{pmatrix} y_{i - 1} \\ y_{i - 2} \\ \vdots \\ y_{i - k} \end{pmatrix}$↵
↵
Тогда ↵
↵
$\begin{pmatrix} y_{n} \\ y_{n - 1} \\ \vdots \\ y_{n - k + 1} \end{pmatrix} = \begin{pmatrix} b_{1} & b_{2} & b_{3} & \dots & b_{k - 1}& b_{k} \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \end{pmatrix} ^{n - k} *\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} $↵
↵
После того, как мы нашли $y_{n}$ используя бинарное возведение матрицы в степень, нам надо решить ↵
↵
$x^{y_{n}}\equiv m\mod{p}$↵
↵
Заметим, что число $3$ является первообразным корнем числа $998244353$ (степени тройки имеют все возможные остатки по модулю $p$)↵
↵
Значит для какого-либо $k$ выполняется $3^k\equiv x\mod{p}$↵
↵
Из этого следует что для такого $k$ верно и $(3^k)^{y_{n}}\equiv m\mod{p}$ а значит и $(3^{y_{n}})^k\equiv m\mod{p}$↵
↵
Найдем $k$, которое подходит под эти свойства.↵
↵
Обозначим за $inv(i)$ элемент, обратный i по модулю $p$.↵
↵
Число $k$ представимо в виде $k = f * d + s$, где $f > s$. Возьмем число $f$ примерно равное $\sqrt{p}$ и будем перебирать $d$. Для каждого $d$ необходимо проверить, существует ли подходящее $s$. Для этого мы предподсчитаем остатки от деления всех степеней от $0$ до $f - 1$ числа $3^{y_{n}}$ на $p$.↵
↵
$(3^{y_{n}})^{f * d + s} = (3^{y_{n}})^{f * d} * (3^{y_{n}})^{s} = m \mod{p}$↵
↵
Преобразуем ↵
↵
$(3^{y_{n}})^{s} = inv((3^{y_{n}})^{f * d} * inv(m))\mod{p}$↵
↵
↵
Теперь чтобы проверить, что для данного $d$ есть подходящее $s$ надо просто посмотреть, был ли у какой-то степени $s$ числа $3^{y_{n}}$ такой остаток от деления на $p$, и если был, то найти такое $s$. Тогда $k = f * d + s$, a $x = 3^{k}\mod{p}$.↵
↵
Если же после всех итераций по $d$ такого $k$ не нашлось, то ответ — $-1$↵
↵
Код:[submission:49321335]
------------------↵
↵
Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.↵
↵
Асимптотика $O(n ^ 2)$↵
↵
Код:[submission:49284766]↵
↵
[problem:1106B]↵
------------------↵
↵
Заметим, что каждый человек получит либо $d_{j}$ блюд типа $t_{j}$, либо $r_{t_{j}}$ блюд типа $t_{j}$ и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.↵
↵
Асимптотика $O((n + m)\log{}n)$↵
↵
Код:[submission:49285005]↵
↵
[problem:1106C]↵
------------------↵
↵
Для начала заметим, что в каждой группе должно быть ровно два элемента, так как $(a + b) ^ 2 > a ^ 2 + b ^ 2$ для положительных $a$ и $b$↵
↵
Покажем, что $a_{i}$ и $b_{i}$ должны стоять на "противоположных" позициях в отсортированном массиве, так как↵
↵
$\sum_{i = 1}^{n / 2} (a_{i} + b_{j})^2 = \sum_{i = 1}^{n / 2} a_{i}^2 + \sum_{i = 1}^{n / 2} b_{j}^2 + \sum_{i = 1}^{n / 2}\sum_{j = 1} ^ {n / 2} a_{i} * b_{j}$↵
↵
То есть нам надо минимизировать третье слагаемое. Теперь такой выбор $a_{i}$ и $b_{i}$ следует из транснеравенства ([доказательтво](https://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/55_nerav3_lect.pdf)).↵
↵
Асимптотика $O(n\log{}n)$↵
↵
Код:[submission:49285168]↵
↵
[problem:1106D]↵
------------------↵
↵
Допустим, мы знаем префикс ответа длины $i$. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером. ↵
↵
Это можно сделать используя bfs с приоритетной очередью.↵
↵
Асимптотика $O(n\log{}n + m)$↵
↵
Код:[submission:49285447]↵
↵
↵
[problem:1106E]↵
------------------↵
↵
Задача решается методом динамического программирования. Обозначим за $dp[i][j]$ минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени $i$ и Алиса уже отвлекла его $j$ раз.↵
↵
Тогда из $dp[i][j]$ можно перейти в $dp[i + 1][j + 1]$ (если Алиса отвлекает его на $i$-том ходе) и в $dp[d_choice + 1][j]$, где $d_{choice}$ — $d$ конверта, который выберет Боб.↵
↵
Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию $w$. Тогда мы сможем узнавать выбор Боба на каждой итерации за $O(\log{}n)$.↵
↵
Асимптотика $O(n\log{}k + n * m)$↵
↵
Код:[submission:49285694]↵
↵
[problem:1106F]↵
------------------↵
↵
Допустим $f_{k} = x$ и $f_{i} = x^{y_{i}}$. По малой теореме Ферма $a^b\equiv (a^{b\mod{p - 1}})\mod{p}$. Значит мы можем считать $y_{i}$ по модулю $p - 1$. Найдем $y_{n}$ с помощью возведения матрицы в степень.↵
↵
$\relax y_{i} = (b_{1} * y_{i - 1} + b_{2} * y_{i - 2} + \ldots + b_{k} * y_{i - k})\mod{p - 1}$↵
↵
Причем $\relax y_{1} = 0, y_{2} = 0, \dots, y_{k - 1} = 0, y_{k} = 1$↵
↵
$\begin{pmatrix} y_{i} \\ y_{i - 1} \\ \vdots \\ y_{i - k + 1} \end{pmatrix} = \begin{pmatrix} b_{1} & b_{2} & b_{3} & \dots & b_{k - 1}& b_{k} \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \end{pmatrix} * \begin{pmatrix} y_{i - 1} \\ y_{i - 2} \\ \vdots \\ y_{i - k} \end{pmatrix}$↵
↵
Тогда ↵
↵
$\begin{pmatrix} y_{n} \\ y_{n - 1} \\ \vdots \\ y_{n - k + 1} \end{pmatrix} = \begin{pmatrix} b_{1} & b_{2} & b_{3} & \dots & b_{k - 1}& b_{k} \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \end{pmatrix} ^{n - k} *\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} $↵
↵
После того, как мы нашли $y_{n}$ используя бинарное возведение матрицы в степень, нам надо решить ↵
↵
$x^{y_{n}}\equiv m\mod{p}$↵
↵
Заметим, что число $3$ является первообразным корнем числа $998244353$ (степени тройки имеют все возможные остатки по модулю $p$)↵
↵
Значит для какого-либо $k$ выполняется $3^k\equiv x\mod{p}$↵
↵
Из этого следует что для такого $k$ верно и $(3^k)^{y_{n}}\equiv m\mod{p}$ а значит и $(3^{y_{n}})^k\equiv m\mod{p}$↵
↵
Найдем $k$, которое подходит под эти свойства.↵
↵
Обозначим за $inv(i)$ элемент, обратный i по модулю $p$.↵
↵
Число $k$ представимо в виде $k = f * d + s$, где $f > s$. Возьмем число $f$ примерно равное $\sqrt{p}$ и будем перебирать $d$. Для каждого $d$ необходимо проверить, существует ли подходящее $s$. Для этого мы предподсчитаем остатки от деления всех степеней от $0$ до $f - 1$ числа $3^{y_{n}}$ на $p$.↵
↵
$(3^{y_{n}})^{f * d + s} = (3^{y_{n}})^{f * d} * (3^{y_{n}})^{s} = m \mod{p}$↵
↵
Преобразуем ↵
↵
$(3^{y_{n}})^{s} = inv((3^{y_{n}})^{f * d} * inv(m))\mod{p}$↵
↵
↵
Теперь чтобы проверить, что для данного $d$ есть подходящее $s$ надо просто посмотреть, был ли у какой-то степени $s$ числа $3^{y_{n}}$ такой остаток от деления на $p$, и если был, то найти такое $s$. Тогда $k = f * d + s$, a $x = 3^{k}\mod{p}$.↵
↵
Если же после всех итераций по $d$ такого $k$ не нашлось, то ответ — $-1$↵
↵
Код:[submission:49321335]
