Как строится последовательность $$$a$$$? В условии написано, что $$$a_{i+2}=a_{i}\mod a_{i+1}$$$ Каким свойством тогда должна обладать последовательность $$$a$$$?

По построению, получается, что $$$a_i \ge a_{i+1}$$$, то есть последовательность должна быть отсортирована по невозрастанию. Как тогда решать всю задачу?

Тогда мы можем отсортировать последовательность $$$b$$$ по невозрастанию и проверить, что $$$b_{i+2}=b_{i}\mod b_{i+1}$$$

Какие самые простые числа являются палиндромами?

Это числа, состоящие из одной цифры. Когда мы можем так сделать? Как мы можем использовать свойство числа $$$b$$$?

Мы знаем, что число $$$b$$$ делится на $$$12$$$, тогда $$$b = (n - a)$$$ тоже делится на $$$12$$$. Тогда что мы знаем про число $$$a$$$?

Мы знаем остаток от деления числа $$$a$$$ на $$$12$$$, он равен остатку от деления числа $$$n$$$ на $$$12$$$, потому что $$$n-a\equiv\pmod{12}$$$, значит $$$n\equiv a\pmod{12}$$$. Пусть $$$r$$$ — остаток от деления. Тогда какие числа мы можем использовать в качестве числа $$$a$$$?

$$$a \in {r, r + 12, r + 24, r + 36, \ldots, r + 12\cdot i, \ldots}$$$. Что если $$$r \lt 10$$$?

Тогда мы можем взять $$$a = r$$$, потому что число $$$a$$$ в таком случае будет состоять из одной цифры. А что если $$$r \in {10, 11}$$$?

Если $$$r = 11$$$, то опять можем взять $$$a = r = 11$$$, потому что $$$11$$$ уже палиндром. Остался случай $$$r = 10$$$. Что делать с ним?

Если $$$r = 10$$$, тогда $$$a \in {10, 22, 34, 46, \ldots}$$$. Какое $$$a$$$ можем взять?

Можем взять $$$a = 22$$$. На самом деле, теперь мы видим, что если ответ есть, то можем выбрать $$$a \le 22$$$, тогда можем просто перебрать $$$a$$$ и проверить, что $$$(n - a)\equiv 0\pmod{12}$$$ и $$$a$$$ палиндром.

Первое, на что я обратил внимание — это ограничения. Они позволяют решить задачу за $$$O(n^2)$$$, тогда мы можем для каждого $$$i$$$ решить задачу за $$$O(n)$$$.

Давайте разберем случай, когда $$$i=1$$$, тогда остальные можно решить аналогично. Итак, мы хотим, чтобы $$$w_1=0$$$, а также чтобы выполнялись условия сообщающихся сосудов. Сейчас в задаче циклическое условие, какую более простую задачу можно решить?

Можно попробовать решить задачу, где наше условие не цикличное. Как это сделать?

Как выбрать $$$w_2$$$?

Можно взять $$$w_2=h_2$$$, но тогда возможно сломается условие для $$$h_2$$$. Как выбрать $$$w_3$$$?

Можем взять $$$w_3 = \max(w_2,h_2)$$$, тогда что будет если $$$w_2 \gt h_2$$$?

Тогда $$$w_3 = w_2$$$ и условие сохранилось, тогда как выбрать $$$w_{i+1}$$$, если мы знаем $$$w_i$$$?

Можем взять $$$w_{i+1}=\max(w_i, h_i)$$$. То есть по сути мы строим массив префиксных максимумов массива $$$h$$$. Что в таком случае у нас ломается?

Сломаться может условие на $$$h_n$$$, потому что в исходной задаче мы имеет цикличные условия. То есть может быть так, что $$$w_n$$$ слишком большой, а т.к. $$$w_1=0$$$, то возможно, что $$$w_n \gt h_n$$$ и $$$w_n\neq w_1$$$. Как будет выглядеть наш полученный массив $$$w$$$? На какой элемент в массиве $$$h$$$ можно обратить внимание?

На максимальный элемент, пусть он расположен в $$$h_q$$$. После $$$q$$$-го элемента все элементы будут равны. Какой аналогичный простой шаг мы можем сделать?

Мы можем построить массив суффиксных максимумов, тогда возможно сломается условие на $$$h_1$$$ из-за того, что $$$w_2$$$ будет слишком большим. Как мы можем тогда решить задачу?

В качестве финального $$$w$$$ мы можем взять минимум из двух ответов — префиксного максимума и суффиксного максимума.

Попробую проэмулировать несколько первых шагов. Изначально нам известны числа на позициях $$${1, 2^k+1}$$$, после первого шага нам будут известны числа на позициях $$${1, 2^{k-1}+1, 2^k+1}$$$. Что будет еще на следующем шаге?

Нам будут известны числа на позициях $$${1, 2^{k-2}+1,2^{k-1}+1,2^{k-2}+2^{k-1}+1}$$$. Чем равно расстояние между соседними индексами?

До шагов расстояние равно $$$2^k+1-1=2^k$$$, на первом шаге расстояние равно $$$2^{k-1}+1-1=2^k+1-(2^{k-1}+1)=2^{k-1}$$$. Какое будет расстояние между индексами на следующем шаге?

Оно будет равно $$$2^{k-2}$$$ и так далее. Мы хотим посчитать $$$\sum_i x_i\cdot y_i$$$, как можно вычислить $$$y_i$$$, зная только $$$x_i$$$?

Можно вычислить так: $$$y_i = n - x_i$$$, тогда вся сумма будет равна $$$n\sum_i x_i - \left(\sum_i x_i^2\right)$$$. Как вычислить $$$\sum_i x_i$$$? Какой физический смысл у этой суммы?

Эта сумма считает общее количество бит по всем элементам массив, можно ли это как-то перефразировать?

Пусть $$$F(j)$$$ — количество элементов в массиве $$$a$$$, у которых $$$j$$$-й бит равен единице? Тогда чему равна вся сумма?

Вся сумма равна $$$\sum_j F(j)$$$. Как посчитать $$$F(j)$$$ для конкретного $$$j$$$? От чего зависит эта величина?

Эта величина зависит от того, что находится в $$$j$$$-м бите у чисел $$$a_1, a_{2^k+1}$$$. И размера массива.

Такую величину можно посчитать с помощью динамического программирования $$$F_{l, x, y}$$$ -- количество ежиниц в массиве $$$a$$$, если этот массив будет состоять из $$$2^l+1$$$ элементов, а первый и последний элемент будут равны $$$x$$$ и $$$y$$$ соответственно. Какая База динамики?

База динамики такая: $$$F_{0,x,y}=x+y$$$. А где будет лежать ответ?

Пусть $$$cnt_{x,y}$$$ — количество бит, что в $$$a_1$$$ лежит бит $$$x$$$, а в $$$a_{2^k+1}$$$ лежит бит $$$y$$$. Тогда $$$\sum_i x_i = \sum_{x=0}^{1}\sum_{y=0}^{1}cnt_{x,y}\cdot F_{k,x,y}$$$. Осталось только посчитать переход динамики.

Допустим, мы знаем ответ для слоя $$$l$$$, то есть знаем значения $$$F_{l,x,y}$$$ для любых $$$x,y$$$. Как посчитать $$$F_{l+1,x,y}$$$? Мы знаем, что мы должны рассмотреть середину и положить туда число $$$z=x\oplus y$$$

Тогда $$$F_{l+1,x,y}=F_{l,x,z}+F_{l,z,y}-z$$$, потому что мы поделим массив на две части и два раз посчитаем $$$z$$$, поэтому его нужно один раз вычесть из ответа.

Хорошо, как теперь посчитать $$$\sum_i x_i^2$$$? Какой физический смысл этой величины?

Физический смысл этой величины такой: по сути мы перебираем все пары бит $$$p,q$$$ и добавляем единицу, если в $$$p$$$-м бите и в $$$q$$$-м бите стоят единицы. Как тогда это посчитать?

Опять с помощью динамики $$$G_{l,x,y,z,w}$$$ — это количество элементов финального массива (причем все элементы состоят из двух бит), что в этих элементах в обоих битах стоят единицы. Причем первый элемент содержит биты $$${x,y}$$$, а последний элемент содержит биты $$${z,w}$$$. Какая база динамики?

База динамики: $$$G_{0,x,y,z,w}=xy+zw$$$. А как посчитать ответ?

Ответ можно посчитать так: $$$\sum_i x_i^2 = \sum_{x=0}^{1}\sum_{y=0}^{1}\sum_{z=0}^{1}\sum_{w=0}^{1}cnt_{x,z}\cdot cnt_{y,w}\cdot G_{k,x,y,z,w}$$$. Осталось только разобраться с переходом.

Мы хотим найти $$$G_{l+1}$$$ по $$$G_l$$$. Оять мы выделяем середину, в которой будут лежать биты $$${u=x\oplus z, v=y\oplus w}$$$. Тогда $$$G_{l+1,x,y,z,w}=G_{l,x,y,u,v}+G_{l,u,v,z,w}-u\cdot v$$$.

Итак, мы знаем, что $$$a_i$$$ — количество отрезков, в которых $$$p_i$$$ является минимумом. Представим, что мы смотрим на какую-то перестановку, на какой элемент можно обратить внимание?

На минимальный элемент, пусть он находится в позиции $$$i$$$, тогда сколько отрезков его покрывает?

Его покрывает $$$i\cdot (n-i+1)$$$ (в 1-индексации). Как нам найти позицию, где лежит минимумум? А что если их несколько?

Все позиции, где $$$a_i=i\cdot(n-i+1)$$$ потенциальные позиции для минимума. Если таких нет, то ответ 0, а если их несколько? Тогда ответ тоже 0, потому что в перестановке только один минимум. Хорошо, тогда пусть мы смогли найти позицию минимума $$$i$$$. Тогда левее этого элемента находится $$$c_l=i-1$$$ элементов, а правее $$$c_r=n-i$$$. Зависят ли элементы из левой части от элементов из правой части?

Не завсият, тогда мы можем распределить осташивеся $$$(n-1)$$$ элементов по этим частям любым способом и рекурсивно решить задачу для обеих частей. Сколько есть способов распределить $$$(n-1)$$$ элементов по обеим частям?

Всего есть $$$\binom{c_l+c_r}{c_l}$$$ способов. Если количество перестановок в левой части равно $$$L$$$, а в правой часте равно $$$R$$$, тогда чему равен итоговый ответ?

Он равен $$$\binom{c_l+c_r}{c_l}\cdot L\cdot R$$$. Осталось только понять, как находить минимальный иднекс $$$i$$$? Что будет если мы каждый раз будем находить его ближе к конце массива, какое время работы будет в худшем случае?

Оно будет равно $$$n+(n-1)+(n-2)+\ldots + 1=O(n^2)$$$. А если мы будм находить его всегда в $$$i \le n / 2$$$.

Тогда время работы можно оценить так $$$T(n)=T(c_l)+T(c_r)+\min(c_l,c_r) \le 2T(n/2)+O(n)=O(n\log{n})$$$. Это называется мастер-теорема

Из задачи $$$C$$$ мы знаем, что для каждого $$$i$$$ мы ищем префиксные и суффиксные максимумы и считаем сумму минимумов из двух ответов. Чтобы удобнее было работать, давайте удвоим массив $$$h$$$, то есть увеличим его в два раза и сделаем $$$h_{i+n}=h_i$$$. Тогда при работе с ответов для $$$i$$$-го индекса нам нужно будет решать задачу для подотрезка $$$[i, i + n)$$$. В каком месте префиксные максимумы перестают меняться?

Префиксные максимумы, как и суффиксные перестают меняться в максимамльном элементе $$$h_q$$$. Как его быстро найти для всех подотрезков $$$[i, i + n)$$$?

Пусть $$$h_z$$$ — первый максимум во всем массиве $$$h$$$, тогда $$$q = z$$$ или $$$q = z + n$$$. Тогда по сути нам нужно стартонуть с элемента $$$i$$$ и идти до элемента $$$q$$$, поддерживая максимум и считая сумму этих максимумов. Аналогично, нам нужно стартонуть с элемента $$$i + n - 1$$$ и идти до $$$q$$$, поддерживая максимум. Тогда нам нужно научиться для массива $$$h$$$ и индекса $$$q$$$ считать массив $$$R_j,j \ge q$$$ — сумма максимумов, если мы начнем с $$$j$$$-го элемента и будем идти до элемента $$$q$$$. Как можно это сделать?

Для начала можно сделать $$$R_j=R_{j-1}+h_j$$$, но тогда мы упустим ответ, если $$$h_j \gt h_{j-1}$$$. На какой элемент слева от $$$j$$$ нам нужно смотреть?

Нам нужно найти ближайший слева элемент $$$v \lt j$$$, что $$$h_v \ge h_j$$$, тогда чему будет равен $$$R_j$$$?

Он будет равен $$$R_j=R_{v}+(j-v)\cdot h_j$$$. Как найти $$$v$$$?

С помощью стека, будем идти слева направо и поддерживать некоторое множество индексов. Пусть мы рассматриваем индекс $$$j$$$, тогда нам нужно снять с вершины стека все индекс, значения в которых меньше $$$h_j$$$, тогда после этого на вершине стека будет как раз ближайший слева элемент $$$h_v \ge h_j$$$.