Всем Привет!↵
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражнения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из своей головы и записали/нарисовали максимальное количество идей и больше уже ничего не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерировать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен к разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Разработка ИИ-проекта↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Судя по всему, нужно аккуратно расписать формулы в соответствии с условием задачи. Предположим, что мы знаем, что ответ равен $T$. Какие на него есть условия, когда Никита не использует ИИ? Сколько строк кода напишут ребята?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Они напишут $T\cdot (x + y)$ строк кода и мы хотим, чтобы выполялось $T\cdot (x + y) \ge n$, тогда $T \ge \frac{n}{x+y}$. А что если они будут использовать ИИ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда они напишут $T\cdot x + (T-z)\cdot 10\cdot y$ строк. Какое тогда есть ограничение на $T$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
$T\cdot x + (T-z)\cdot 10\cdot y \ge n$, тогда $T\cdot(x+10y) \ge n + 10zy$, тогда $T \ge \frac{n + 10zy}{x+10y}$. ↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Выбираем максимум из двух выражений и округляем вверх.↵
</spoiler>↵
↵
Решение: [submission:377920759]↵
↵
↵
B. Различные расстояния↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Какой самый простой случай можно рассмотреть?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Когда $n=2$. Как его решить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Обозначим два числа за $X,Y$, тогда можно взять например такой ответ: "XYYXXYXY", тогда для $X$ расстояния образуют множество $(3,1,2)$, а у $Y$ множество $(1,3,2)$. Как теперь решить для случая $n=3$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Можно например взять ответ из прмеров или например такую строку: "XYZXXZXYYZZY". Как теперь решить задачу для четных $n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Можно разбить числа на пары $(1,2),(3,4),\ldots,(n-1,n)$, для каждой пары мы можем построить блок длины $8$, останется их только склеить. А как решить задачу для нечетных $n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Если $n$ нечетное, то $n \ge 3$, тогда мы можем построить блок для чисел $(n-2,n-1,n)$ длины $12$. Нам остается только решить задачу для оставшихся $(n-3)$ чисел. А это мы уже умеем делать, т.к. $(n-3)$ — четное число.↵
</spoiler>↵
↵
Решение: [submission:377932509]↵
↵
C. Стоимость скобочной последовательности↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что обратил внимание — это ограничения задачи, которые позволяют ее решить за $O(n^2)$, то есть можно что-нибудь перебрать за $O(n)$, а дальше посчитать что-то за $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
У нас есть скобки всего двух типов: "(" и ")". Пусть мы удалим $x$ скобок "(" и $y$ скобок ")", тогда $x+y \le k$. Какие скобки типа "(" нам выгоднее всего удалять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Нам выгоднее всего удалить $x$ самых левых скобок "(", почему?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Посмторим на оптимальный ответ. В нем мы можем найти ПСП какой-то длины. Посмотрим на первый символ этой ПСП, он равен "(", причем мы можем считать, что это самая первая скобка в строке (если это не так, тогда мы можем заменить первый символ на скобку "(" левее). Т.к. мы предположили, что мы удалили не $x$ самых левых скобок "(", тогда есть удаленная скобка, которая правее скобки "(" в ПСП, мы можем вместо удаления этой более правой скобки удалить скобку из ПСП, тогда сама ПСП не увеличится.↵
↵
Хорошо, а какие тогда скобки ")" нам выгоднее всего удалять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам выгоднее всего удалять $y$ самых правых скобок ")". Как тогда решать задачу? Что можно перебрать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Мы можем перебрать $x$ за $O(n)$, тогда $y=k-x$. Остается только удалить скобки за $O(n)$ и посчитать длину максимальной ПСП в оставшейся строке. Как это сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Можно это сделать жадно. Будем идти слева направо и поддерживать текущее количество скобок "(" без парной ")" (пусть это число равно $b$), а также количество уже спаренных скобок (это и есть длина ПСП). Если текущий символ "(", что тогда можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Можем увеличить $b$ на единицу, а если текущий символ — это ")"?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Тогда мы можем попытаться спарить эту скобку с какой-то из "(". То есть, если $b > 0$, то мы можем уменьшить $b$ на единицу и увеличить ответ на $2$.↵
</spoiler>↵
↵
Решение: [submission:377946709]↵
↵
D. Товары на полке↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что обратил внимание, что мы можем сжать координаты и считать, что $0 \le a_i < n$. Тогда для каждого $0 \le x < n$ мы можем выписать все позиции $i$, что $a_i=x$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Как нам для конкретного $x$ проверить, что все числа в массиве $a_i=x$ образуют один отрезок?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть $l$ — минимальная позиция $a_l=x$, а $r$ — максимльная, пусть $c$ — количество элементов в массиве, равных $x$. Как проверить условие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Достаточно проверить, что $r - l + 1 = c$. Хорошо, теперь какой бывает простой случай?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Пусть $F(x) = 1$, если $x$ образует единый отрезок и $0$ иначе. Тогда простой случай, когда $F(x)=1$ для всех $x$. Хорошо, осталося случай, когда есть какой-то $y$, что $F(y)=0$. Что тогда? Какую позицию тогда точно нужно будет поменять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Тогда мы знаем, что $r-l+1 > c$ и есть "дырки", то есть позиции, в которых стоят какие-то другие числа. В таком случае мы будем обязаны обменять местами либо $l$, либо $r$ с кем-то другим, т.к. иначе величина $r-l+1$ может только увеличиться, а $c$ не изменится. Тогда сколько всего можно перебрать пар для обмена местами?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Мы можем перебрать пары $(l,i),(r,i)$ для всех $i$, то есть всего есть $O(n)$ пар. Как нам для конкретной пары проверить, помогает ли она или нет?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Мы можем поддерживать множество позиций в `std::set<int>`, тогда операцию `swap` и проверку конкретного $x$ можно еализовать за $O(\log{n})$. Как тогда решить задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Давайте поддерживать количество $x$, что $F(x)=0$↵
Давайте переберем все пары для `swap` , сделаем этот `swap` и обновим количество плохих $x$-ов. Если помогло, то выводим ответ, а иначе меняем обратно, возвращая все на место и идем дальше.↵
</spoiler>↵
↵
Решение: [submission:377946709]↵
↵
E1. Передача перестановки (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Зафиксирую конкетную перестановку бит из условия. Какие простые условия можно проверить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы хотим, чтобы не было нуля, а также чтобы все числа были разные. Тогда какое единственное условие может быть нарушено?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Скажем, что перестановка бит хорошая, если максимальный элемент после перестановки бит не больше $n$. Тогда чему равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Он равен количеству хороших перестановок, потому что разные перестановки бит дают разные перестановки массива $p$. Можем ли мы перебрать все перестановки бит $a_0,a_1,\ldots,a_{k-1}$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Да, можем, потому что $\log_2(n) \le 11$, а $11! \le 4\cdot 10^7$. Что останется сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Останется проверить, что для конкретной перестановки бит все числа будут не больше $n$. Что значит, что число $x$ больше числа $n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Это когда мы сравниваем два числа начиная со старших бит и находим первое несовпадение в бите $j$ и так оказывается, что $n_j=0,x_j=1$, то есть $j$-й бит числа $n$ равен нулю, а у числа $x$ он равен единице.↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Тогда мы можем перебирать биты начиная со старшего, пусть смотрим на бит $j$, тогда мы хотим проверить, есть ли число $x$, что в битах $a_q$ (здесь $q > j$) в нем стоит то же самое, что в бите $q$ числа $n$, а в бите $a_q$ стоит единица, в то время как у $n$ стоит ноль. Как мы можем это проверить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Перебирая биты мы можем поддерживать маску бит, которые нам интересны, а также строить желаемое число которое мы хотим получить. Дальше мы можем запомнить для каждой маски, какие есть числа в исходном массиве, если мы хотим рассматривать только биты из конкретной маски.↵
</spoiler>↵
↵
Решение: [submission:377975138]
↵
↵
↵
Меня зовут Максим и я очень давно хочу достичь рейтинга 3000. Я верю, что для этого мне надо научиться мыслить, как человек, у которого уже есть 3000 рейтинга. Очень часто в разборах пишут фразы "заметим, что..." или "докажем вот такой факт..." и дальше идет долгое доказательство этого факта. А то, каким образом я должен к этому факту прийти, как эта мысль должна зародиться у меня в голове, никто нигде не пишет. Я думаю, что не только у меня есть эта проблема, поэтому вместо того, чтобы ждать понятный разбор, я решил начать с себя. Именно поэтому, я решил написать пошаговый разбор, где я буду описывать ход своих мыслей и действий, которые позволяют мне придумать эти самые идеи.↵
↵
Также, я создал группу по прокачке навыков спортивного программирования для людей с рейтингом 1200- , чтобы помочь им стать лучше и достигнуть рейтинга 1500+. Если хотите больше об этом узнать, рекомендую прочитать [ЭТОТ ПОСТ](https://codeforces.me/blog/entry/153213) или заполнить [ФОРМУ](https://forms.yandex.ru/u/69ea4ba0493639794fd019d8). Эту группу я назвал **Polaris** в честь путеводной звезды. В Polaris ребята решают специально подобранные контесты под их уровень, дорешивают их с помощью пошаговых разборов, изучают новую теорию, решают специально подготовленные для них подводящие упражнения, а также получают подробные рекомендации на основе их участия в тренировочных контестах. Более того, специально для участников группы я делаю пошаговые разборы тех задач, которые интересны самим участникам. Также, в группе регулярно ведется обсуждение прошедших контестов, а в ближайшем будущем мы будем готовиться к предстоящим олимпиадам (как школьным, так и студенческим). Присоединяйтесь, я буду вам очень рад!↵
↵
А теперь перейдем к самому разбору контеста. Но перед этим, я бы хотел ввести несколько правил чтения разбора для того, чтобы вы смогли получить максимум пользы от него.↵
↵
1. Перед чтением разбора задачи, убедитесь, что вы прочитали задачу, подумали над ней, извлекли из своей головы и записали/нарисовали максимальное количество идей и больше уже ничего не можете придумать.↵
2. Во время чтения разбора, если в какой-то момент, какое-то предложение в разборе навело вас на новую мысль, перестаньте читать разбор и вернитесь к пункту (1), а именно продолжите с этого места генерировать новые идеи. Это очень важно.↵
3. Если вы дочитали текст разбора до конца и не поняли, как решать задачу или остались вопросы, то их нужно обязательно задать в комментариях или спросить в Polaris. Там вам помогут я и ребята, кто справился с этой задачей. Также в этом случае, полезно прочитать код, который будет прикреплен к разбору.↵
4. После того, как вы решили задачу, обязательно посмотрите код других участников и код с разбора. Возможно, он наведет вас на мысль о том, как можно было проще и быстрее реализовать решение задачи.↵
↵
A. Разработка ИИ-проекта↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Судя по всему, нужно аккуратно расписать формулы в соответствии с условием задачи. Предположим, что мы знаем, что ответ равен $T$. Какие на него есть условия, когда Никита не использует ИИ? Сколько строк кода напишут ребята?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Они напишут $T\cdot (x + y)$ строк кода и мы хотим, чтобы выполялось $T\cdot (x + y) \ge n$, тогда $T \ge \frac{n}{x+y}$. А что если они будут использовать ИИ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Тогда они напишут $T\cdot x + (T-z)\cdot 10\cdot y$ строк. Какое тогда есть ограничение на $T$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
$T\cdot x + (T-z)\cdot 10\cdot y \ge n$, тогда $T\cdot(x+10y) \ge n + 10zy$, тогда $T \ge \frac{n + 10zy}{x+10y}$. ↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Выбираем максимум из двух выражений и округляем вверх.↵
</spoiler>↵
↵
Решение: [submission:377920759]↵
↵
↵
B. Различные расстояния↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Какой самый простой случай можно рассмотреть?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Когда $n=2$. Как его решить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Обозначим два числа за $X,Y$, тогда можно взять например такой ответ: "XYYXXYXY", тогда для $X$ расстояния образуют множество $(3,1,2)$, а у $Y$ множество $(1,3,2)$. Как теперь решить для случая $n=3$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Можно например взять ответ из прмеров или например такую строку: "XYZXXZXYYZZY". Как теперь решить задачу для четных $n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Можно разбить числа на пары $(1,2),(3,4),\ldots,(n-1,n)$, для каждой пары мы можем построить блок длины $8$, останется их только склеить. А как решить задачу для нечетных $n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Если $n$ нечетное, то $n \ge 3$, тогда мы можем построить блок для чисел $(n-2,n-1,n)$ длины $12$. Нам остается только решить задачу для оставшихся $(n-3)$ чисел. А это мы уже умеем делать, т.к. $(n-3)$ — четное число.↵
</spoiler>↵
↵
Решение: [submission:377932509]↵
↵
C. Стоимость скобочной последовательности↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что обратил внимание — это ограничения задачи, которые позволяют ее решить за $O(n^2)$, то есть можно что-нибудь перебрать за $O(n)$, а дальше посчитать что-то за $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
У нас есть скобки всего двух типов: "(" и ")". Пусть мы удалим $x$ скобок "(" и $y$ скобок ")", тогда $x+y \le k$. Какие скобки типа "(" нам выгоднее всего удалять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Нам выгоднее всего удалить $x$ самых левых скобок "(", почему?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Посмторим на оптимальный ответ. В нем мы можем найти ПСП какой-то длины. Посмотрим на первый символ этой ПСП, он равен "(", причем мы можем считать, что это самая первая скобка в строке (если это не так, тогда мы можем заменить первый символ на скобку "(" левее). Т.к. мы предположили, что мы удалили не $x$ самых левых скобок "(", тогда есть удаленная скобка, которая правее скобки "(" в ПСП, мы можем вместо удаления этой более правой скобки удалить скобку из ПСП, тогда сама ПСП не увеличится.↵
↵
Хорошо, а какие тогда скобки ")" нам выгоднее всего удалять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Нам выгоднее всего удалять $y$ самых правых скобок ")". Как тогда решать задачу? Что можно перебрать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Мы можем перебрать $x$ за $O(n)$, тогда $y=k-x$. Остается только удалить скобки за $O(n)$ и посчитать длину максимальной ПСП в оставшейся строке. Как это сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Можно это сделать жадно. Будем идти слева направо и поддерживать текущее количество скобок "(" без парной ")" (пусть это число равно $b$), а также количество уже спаренных скобок (это и есть длина ПСП). Если текущий символ "(", что тогда можем сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Можем увеличить $b$ на единицу, а если текущий символ — это ")"?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Тогда мы можем попытаться спарить эту скобку с какой-то из "(". То есть, если $b > 0$, то мы можем уменьшить $b$ на единицу и увеличить ответ на $2$.↵
</spoiler>↵
↵
Решение: [submission:377946709]↵
↵
D. Товары на полке↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Первое, на что обратил внимание, что мы можем сжать координаты и считать, что $0 \le a_i < n$. Тогда для каждого $0 \le x < n$ мы можем выписать все позиции $i$, что $a_i=x$.↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Как нам для конкретного $x$ проверить, что все числа в массиве $a_i=x$ образуют один отрезок?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Пусть $l$ — минимальная позиция $a_l=x$, а $r$ — максимльная, пусть $c$ — количество элементов в массиве, равных $x$. Как проверить условие?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Достаточно проверить, что $r - l + 1 = c$. Хорошо, теперь какой бывает простой случай?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Пусть $F(x) = 1$, если $x$ образует единый отрезок и $0$ иначе. Тогда простой случай, когда $F(x)=1$ для всех $x$. Хорошо, осталося случай, когда есть какой-то $y$, что $F(y)=0$. Что тогда? Какую позицию тогда точно нужно будет поменять?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Тогда мы знаем, что $r-l+1 > c$ и есть "дырки", то есть позиции, в которых стоят какие-то другие числа. В таком случае мы будем обязаны обменять местами либо $l$, либо $r$ с кем-то другим, т.к. иначе величина $r-l+1$ может только увеличиться, а $c$ не изменится. Тогда сколько всего можно перебрать пар для обмена местами?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Мы можем перебрать пары $(l,i),(r,i)$ для всех $i$, то есть всего есть $O(n)$ пар. Как нам для конкретной пары проверить, помогает ли она или нет?↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Мы можем поддерживать множество позиций в `std::set<int>`, тогда операцию `swap` и проверку конкретного $x$ можно еализовать за $O(\log{n})$. Как тогда решить задачу?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Давайте поддерживать количество $x$, что $F(x)=0$↵
Давайте переберем все пары для `swap` , сделаем этот `swap` и обновим количество плохих $x$-ов. Если помогло, то выводим ответ, а иначе меняем обратно, возвращая все на место и идем дальше.↵
</spoiler>↵
↵
Решение: [submission:377946709]↵
↵
E1. Передача перестановки (простая версия)↵
===================↵
↵
<spoiler summary="Шаг 1">↵
Зафиксирую конкетную перестановку бит из условия. Какие простые условия можно проверить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 2">↵
Мы хотим, чтобы не было нуля, а также чтобы все числа были разные. Тогда какое единственное условие может быть нарушено?↵
</spoiler>↵
↵
<spoiler summary="Шаг 3">↵
Скажем, что перестановка бит хорошая, если максимальный элемент после перестановки бит не больше $n$. Тогда чему равен ответ?↵
</spoiler>↵
↵
<spoiler summary="Шаг 4">↵
Он равен количеству хороших перестановок, потому что разные перестановки бит дают разные перестановки массива $p$. Можем ли мы перебрать все перестановки бит $a_0,a_1,\ldots,a_{k-1}$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 5">↵
Да, можем, потому что $\log_2(n) \le 11$, а $11! \le 4\cdot 10^7$. Что останется сделать?↵
</spoiler>↵
↵
<spoiler summary="Шаг 6">↵
Останется проверить, что для конкретной перестановки бит все числа будут не больше $n$. Что значит, что число $x$ больше числа $n$?↵
</spoiler>↵
↵
<spoiler summary="Шаг 7">↵
Это когда мы сравниваем два числа начиная со старших бит и находим первое несовпадение в бите $j$ и так оказывается, что $n_j=0,x_j=1$, то есть $j$-й бит числа $n$ равен нулю, а у числа $x$ он равен единице.↵
</spoiler>↵
↵
<spoiler summary="Шаг 8">↵
Тогда мы можем перебирать биты начиная со старшего, пусть смотрим на бит $j$, тогда мы хотим проверить, есть ли число $x$, что в битах $a_q$ (здесь $q > j$) в нем стоит то же самое, что в бите $q$ числа $n$, а в бите $a_q$ стоит единица, в то время как у $n$ стоит ноль. Как мы можем это проверить?↵
</spoiler>↵
↵
<spoiler summary="Шаг 9">↵
Перебирая биты мы можем поддерживать маску бит, которые нам интересны, а также строить желаемое число которое мы хотим получить. Дальше мы можем запомнить для каждой маски, какие есть числа в исходном массиве, если мы хотим рассматривать только биты из конкретной маски.↵
</spoiler>↵
↵
Решение: [submission:377975138]
