Codeforces Round 723 (Div. 2) |
---|
Закончено |
Однажды Oolimry увидел суффиксный массив. Ему стало интересно, сколько строк могут дать этот суффиксный массив.
Более формально, для данного суффиксного массив длины $$$n$$$ и размера алфавита $$$k$$$, подсчитайте количество строк, которые порождают такой суффиксный массив.
Пусть $$$s$$$ — строка длины $$$n$$$. Тогда $$$i$$$-й суффикс $$$s$$$ — это подстрока $$$s[i \ldots n-1]$$$. Суффиксный массив — это массив целых чисел, которые представляют собой позиции начал всех суффиксов данной строки после сортировки этих суффиксов в лексикографическом порядке. Например, суффиксный массив oolimry — это $$$[3,2,4,1,0,5,6]$$$, так как отсортированный массив суффиксов — это $$$[\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}]$$$.
Строка $$$x$$$ лексикографически меньше строки $$$y$$$, если либо $$$x$$$ является префиксом $$$y$$$ (и $$$x\neq y$$$), либо существует такой $$$i$$$, что $$$x_i < y_i$$$, и для любого $$$1\leq j < i$$$ , $$$x_j = y_j$$$.
Первая строка содержит 2 целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 200000,1 \leq k \leq 200000$$$) — длину суффиксного массива и размер алфавита соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$s_0, s_1, s_2, \ldots, s_{n-1}$$$ ($$$0 \leq s_i \leq n-1$$$) где $$$s_i$$$ — $$$i$$$-й элемент суффиксного массива, т.е. стартовая позиция $$$i$$$-го лексикографически наименьшего суффикса. Гарантируется, что для всех $$$0 \leq i< j \leq n-1$$$, $$$s_i \neq s_j$$$.
Выведите, сколько строк порождают данный суффиксный массив. Поскольку число может быть очень большим, выведите ответ по модулю $$$998244353$$$.
3 2 0 2 1
1
5 1 0 1 2 3 4
0
6 200000 0 1 2 3 4 5
822243495
7 6 3 2 4 1 0 5 6
36
В первом примере «abb» является единственным возможным решением.
Во втором примере можно легко показать, что не существует возможных строк, так как все буквы должны быть одинаковыми.
В четвертом примере одной из возможных строк является «ddbacef».
Пожалуйста, не забывайте выводить свои ответы по модулю $$$998244353$$$.
Название |
---|