Поймите, что ответ зависит только от $$$pos[k]$$$, а не от самого $$$k$$$

Действительно, бинарный поиск будет искать элемент, находящийся на позиции $$$pos[k]$$$ и сделает точно такие же шаги вне зависимости от самого значения $$$k$$$, если массив $$$a$$$ отсортирован. Осталось только посчитать для каждой позиции за сколько шагов бинпоиск до неё дойдёт

Это совсем уж не сложно :)

Давайте просто промоделируем бинпоиск как написано в задаче, только мы будем заходить и в левый и в правый отрезок и запоминать для каждого числа на каком по очереди шаге оно стало медианой рассматриваемого отрезка. Такой алгоритм только подтверждает, что количество итераций зависит от позиции, а не от значения $$$k$$$

Попробуйте посмотреть на эту сумму не через значения $$$k$$$, а через их позиции в массиве

Так как $$$f(a,k,1, n)$$$ зависит только от позиции числа $$$k$$$ в массиве и мы считаем сумму по всем $$$k$$$, это аналогично сумме по всем позициям для массива из различных чисел, так что

Так как мы совсем не опирались на значения массива, и использовали лишь строгое возрастание, то мы можем быстро просуммировать полученные суммы для всех массивов $$$a$$$

Действительно, для каждого строго возрастающего массива сумма значений $$$f$$$ одинакова, поэтому нужно будет лишь умножить сумму для одного массива на количество таких массивов. Здесь становится понятно, что нужно возвращаться к массивам с повторяющимися числами

В более простом случае нам помогал взгляд на сумму через позицию в массиве, на которой бинпоиск останавливается. Давайте попробуем здесь посчитать, на скольких массивах бинпоиск остановится ровно на позиции $$$i$$$

В отличие от строго возрастающих массивов, где для каждой позиции есть бинпоиск, который в ней останавливается, в общем случае это неверно. Например, если массив состоит только из единиц, бинпоиск остановится только на индексе $$$\frac{n - 1}{2}$$$ (в 0-нумерации). На самом деле, бинпоиск, который ищет число $$$k$$$, остановится в позиции $$$i$$$, если $$$a_i = k$$$ и он не остановился ранее. К счастью, до того, как прийти в позицию $$$i$$$, бинпоиск проверял конкретный набор позиций, зависящий только от $$$i$$$. Обозначим его $$$Poses(i)$$$

Итого, нам нужно научиться считать количество массивов, в которых элемент с индексом $$$i$$$ не совпадает ни с одним из элементов с индексом из $$$Poses(i)$$$. Как бы это посчитать?

Давайте сначала попробуем упростить условие. Несмотря на то, что $$$|Poses(i)|$$$ порядка $$$log(n)$$$, это всё равно много и неудобно

Заметим, что массив $$$a$$$ монотонный, а значит, что если для некоторого $$$j \in Poses(i)$$$ и $$$j \lt i$$$ выполнено $$$a_j = a_i$$$, то и для самого правого $$$j \lt i$$$ тоже, а значит можно оставить только его. Аналогично выкинем все $$$j \gt i, j \in Poses(i)$$$, кроме самого левого из них. У нас останется лишь два индекса, обозначим их за $$$l_i$$$ и $$$r_i$$$ соответственно. Замечу также, что они могут и не быть определены. В конце концов, индексов $$$j \lt i$$$ может не существовать

Кажется, что посчитать количество массивов с условием, что значения на каких-то двух индексах не равны значению на третьем индексе — сложновато. А если условие заменить на равенство, то, наоборот, мы уже будем знать, что все промежуточные числа тоже совпадают с $$$a_i$$$. Давайте попробуем посчитать количество всех массивов и вычесть из них неподходящие

Количество всех массивов считается довольно стандартным образом. Давайте сделаем разумую вещь для монотонным массивов — перейдём к массиву разностей $$$d$$$, где $$$d_0$$$ = $$$a_0 - 1$$$, $$$d_i = a_i - a_{i-1}$$$, $$$d_n = m - a_{n-1}$$$. На него есть два условия: $$$d_i \geq 0$$$ и $$$\sum\limits_{i=0}^n d_i = m - 1$$$. А уже количество таких массивов можно вычислить через задачу о шарах и перегородках, по сути это она и есть — если не слышали ранее — обязательно ознакомьтесь, это очень стандартная комбинаторная задача. При помощи предподсчёта факториалов мы сможем считать число сочетаний $$$C(n, k)$$$ за $$$O(1)$$$ и без труда найдём общее число массивов.

А что насчёт количества неподходящих массивов? Если все элементы с $$$a_{l_i}$$$ по $$$a_i$$$ равны, это означает, что в массиве разностей $$$d_{l_i+1} = d_{l_i + 2} = \ldots = d_i$$$, а значит это количество равно количеству массивов с той же суммой $$$m-1$$$, но уже не из $$$n$$$, а из $$$n - (i - l_i)$$$ элементов, так как все оставшиеся равны нулю. И, чтобы формула стала полностью верной, нужно вычесть такое же количество для $$$r_i$$$. Но при этом мы два раза вычтем количество массивов, для которых все элементы с $$$l_i$$$ по $$$r_i$$$ совпадают. Давайте добавим их обратно, посчитав по уже знакомой формуле