Поділимо ряд на голову — перші шматочків — і хвіст. Позначимо через кількість невпорядкованих пар усередині голови, через — усередині хвоста, а через — кількість пар «елемент голови більший за елемент хвоста». Тоді
Після зсуву голова й хвіст міняються місцями, внутрішні пари не змінюються, а перехресні перевертаються всі одразу:
Віднімаючи, отримуємо a - b = 2c - k(n-k), тобто
— число, визначене однозначно. Якщо воно не ціле, від'ємне або більше за k(n-k), відповідь .
Далі все розпадається на добуток трьох незалежних величин:
скільки множин значень голови дають рівно перехресних пар. Це коефіцієнт при q^c у гауссовому біноміальному коефіцієнті \binom{n}{k}_q = \prod_{i=1}^{k}\frac{1 - q^{\,n-k+i}}{1 - q^{\,i}}, який зручно будувати саме за цією формулою: множення на 1 - q^t і ділення на 1 - q^t роблять по одному проходу масиву коефіцієнтів;
скільки перестановок голови мають невпорядкованих пар і скільки перестановок хвоста мають — це числа Маона, порахуйте їх динамікою з префіксними сумами;
лишається просумувати \sum_{i + j = a - c} I_k(i)\,I_{n-k}(j), де доданків не більше \frac{k(k-1)}{2} + 1 \le 191.
Складність: O\!\left(n^2 + k \cdot k(n-k)\right), з великим запасом у межах обмежень.
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.