Автор задачи: Даниил Орешников, разработчик: Константин Бац
Для решения первой подзадачи нужно было сделать несколько переборов. Переберем генетические коды первого и второго Аватаров для рекомбинации, сравним полученный код со всеми кодами в первом поколении. Все существует $$$n$$$ кодов, сравнение двух кодов происходит за $$$\mathcal{O}(n)$$$. Таким образом, сложность такого решения — $$$\mathcal{O}(n^4)$$$.
Во второй подзадаче в строке было не больше двух символов 'b', а все остальные символы были равны 'a'. Рассмотрим случаи:
Получить код без символа 'b' можно рекомбинацией кода, у которого символ 'b' на четной позиции, и кода с символом 'b' на нечетной позиции. Кодов обоих видов $$$\frac{n}{2}$$$, поэтому существует $$$\frac{n^2}{4}$$$ различных пар индексов.
На самом деле, получить код с двумя символами 'b' можно получить из тех же пар индексов, если элементы пар поменять местами. То есть существует столько же ($$$\frac{n^2}{4}$$$) подходящих пар индексов.
Таким образом, ответ в этом случае равен $$$\frac{n^2}{2}$$$.
Заметим, что четные и нечетные позиции любого циклического сдвига сами являются циклическим сдвигом строки «aa...ab» (длины $$$\frac{n}{2}$$$). Тогда сколько есть способов получить строку $$$s$$$ с помощью рекомбинации? Необходимо выбрать два сдвига, у которых 'b' стоит на строго определенных позициях среди четных и нечетных соответственно. И тех, и тех, ровно по $$$2$$$, поэтому всего есть ровно $$$4$$$ способа получить строку $$$s$$$.
Всего есть $$$n^2$$$ пар особей, из них надо вычесть по $$$4$$$ на каждый различный циклический сдвиг $$$s$$$. Всего различных циклических сдвигов $$$s$$$ либо $$$n$$$, либо $$$\frac{n}{2}$$$, если 'b' стоят на расстоянии $$$\neq \frac{n}{2}$$$ или $$$= \frac{n}{2}$$$ соответственно.
Результатом рекомбинации, таким образом, будет либо строка только из букв 'a' (новая), либо строка с двумя буквами 'b' на том же расстоянии, что и в $$$s$$$ (старая), либо строка с четырьмя буквами 'b' (новая).
Чтобы получить строку из всех 'a', каждую из особей для рекомбинации можно выбрать $$$\frac{n}{2}$$$ способами. Чтобы получить строку с четырьмя 'b', тоже. Ответ — $$$\frac{n^2}{2}$$$.
Для решения третьей подзадачи нужно было немного оптимизировать решение первой подзадачи. Давайте предварительно сохраним unordered_set генетические коды в первом поколении, и чтобы проверить, встречался ли полученный код среди кодов в первом поколении, будем использовать не линейный поиск, а запросы к unordered_set. Время работы такого решения будет $$$\mathcal{O}(n^3)$$$.
Для решения предпоследней подзадачи заметим, что чтобы получить какую-то строку $$$q$$$, являющуюся циклическим сдвигом $$$s$$$, в ходе рекомбинации, надо взять два циклических сдвига, у первого из которых символы на нечетных позициях совпадают с символами на нечетных позициях $$$q$$$, а у второго — аналогично с четными позициями.
Посчитаем полиномиальные хеши отдельно на четных позициях строки $$$s$$$, отдельно на нечетных. Соберем хеши всех циклических сдвигов $$$s$$$ и положим их в unordered_set. Теперь, перебирая $$$i$$$ и $$$j$$$ для рекомбинации, будем вычислять соответствующие частичные хеши их четных/нечетных позиций и проверять, лежит ли их сумма в посчитанном множестве. Такое решение работает за $$$\mathcal{O}(n^2)$$$.
Полное решение требует обратного подхода. Заметим, что количество пар особей, дающих новый код, равно $$$n^2 - t$$$, где $$$t$$$ — количество пар особей, дающих код из первого поколения. То есть можно найти количество пар, дающих уже существующий код, а затем вычесть это число из общего количества пар.
Для каждого уникального циклического сдвига строки $$$s$$$ найдем количество способов его получить в ходе рекомбинации. Для этого, обратно предыдущему решению, заведем множество cnt, в котором для каждого хеша циклического сдвига четных/нечетных позиций $$$s$$$ будем хранить количество раз, которое он встречается. Количество способов получить $$$q$$$, некоторый циклический сдвиг $$$s$$$, в таком случае равно $$$\mathtt{cnt.count}(q_{\mathrm{even}}) \cdot \mathtt{cnt.count}(q_{\mathrm{odd}})$$$.
Авторам также известно альтернативное полное решение задачи, использующее префикс-функцию. Для него обратимся к ключевой идее, указанной в решении подзадачи 2.
Найти период строки можно с помощью префикс-функции ($$$p = n - \mathtt{pf}[n]$$$, если он является делителем $$$n$$$, иначе $$$p = n$$$). Аналогично, с помощью алгоритма Кнута-Морриса-Пратта можно проверить, является ли строка $$$s_1$$$ циклическим сдвигом $$$s_0$$$. В конце останется просто посчитать ответ как $$$$$$n^2 - (m_{00} + m_{01}) \cdot (m_{10} + m_{11}) \cdot p\text{.}$$$$$$