Последовательность Туе-Морса-Радецки-Матеуша (Туорса-Радевуша, для краткости) это бесконечная последовательность, получающаяся из конечной последовательности \(\mathrm{gen}\) длины \(d\) и целого числа \(m\), следующим образом:
- В начале мы определяем \(M_0=(0)\).
- На \(k\)-м шаге, \(k \geq 1\), мы определяем \(M_k\) как конкатенацию \(d\) копий \(M_{k-1}\). Однако, каждая из них немного изменяется — в \(i\)-й из них (\(1 \leq i \leq d\)) каждый элемент \(x\) заменяется на \((x+\mathrm{gen}_i) \pmod{m}\).
Например, если \(\mathrm{gen} = (0, \color{blue}{1}, \color{green}{2})\) и \(m = 4\):
- \(M_0 = (0)\),
- \(M_1 = (0, \color{blue}{1}, \color{green}{2})\),
- \(M_2 = (0, 1, 2, \color{blue}{1, 2, 3}, \color{green}{2, 3, 0})\),
- \(M_3 = (0, 1, 2, 1, 2, 3, 2, 3, 0, \color{blue}{1, 2, 3, 2, 3, 0, 3, 0, 1}, \color{green}{2, 3, 0, 3, 0, 1, 0, 1, 2})\), и так далее.
Как можно заметить, при условии, что первый элемент \(\mathrm{gen}\) равен \(0\), каждый последующий шаг порождает последовательность, префиксом которой является последовательность с предыдущего шага. Тогда мы можем определить бесконечную последовательность Туорса-Радевуша \(M_\infty\) как последовательность, получаемую бесконечным применением шага выше. Например, для параметров выше, \(M_\infty = (0, 1, 2, 1, 2, 3, 2, 3, 0, 1, 2, 3, 2, 3, 0, 3, 0, 1, \dots)\).
Матеуш выбрал последовательность \(\mathrm{gen}\) и целое число \(m\), и с помощью них получил последовательность Туорса-Радевуша \(M_\infty\). Затем он выбрал два целых числа \(l\) и \(r\) и записал подпоследовательность этой последовательности: \(A := ((M_\infty)_l, (M_\infty)_{l+1}, \dots, (M_\infty)_r)\).
Обратите внимание, что мы используем нумерацию с \(1\) для \(M_\infty\) и \(A\).
У Матеуша есть его любимая последовательность \(B\) длины \(n\) и хочет узнать, насколько она большая относительно \(A\). Он говорит, что последовательность \(B\) мажорирует последовательность \(X\) длины \(n\) (обозначим как \(B \geq X\)), если для всех \(i \in \{1, 2, \dots, n\}\) выполняется \(B_i \geq X_i\).
Теперь он спрашивает себя, сколько существует целых чисел \(x\) в отрезке \([1, |A| - n + 1]\) таких, что \(B \geq (A_x, A_{x+1}, A_{x+2}, \dots, A_{x+n-1})\). Так как обе последовательности очень большие, то ответить на вопрос, используя только бумагу и ручку, оказалось затруднительно. Не могли бы вы ему помочь?