← 返回题目列表

Codeforces · 1526/E

E. Oolimry 和后缀数组

中文机器翻译题面 查看原题

曾几何时,Oolimry 看到了一个后缀数组。他想知道有多少字符串可以产生这个后缀数组。

更正式地说,给定一个长度为 $$$n$$$ 且字母大小为 $$$k$$$ 的后缀数组,计算生成此类后缀数组的字符串数量。

令 $$$s$$$ 为长度为 $$$n$$$ 的字符串。那么 $$$s$$$ 的第 $$$i$$$ 后缀就是子串 $$$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\neq y$$$),或者存在这样的 $$$i$$$ 使得 $$$x_i < y_i$$$,并且对于任何 $$$1\leq j < i$$$,则字符串 $$$x$$$ 按字典顺序小于字符串 $$$y$$$ ,$$$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$$$ 取模的答案。

示例

输入 #1

3 2
0 2 1

输出 #1

1

输入 #2

5 1
0 1 2 3 4

输出 #2

0

输入 #3

6 200000
0 1 2 3 4 5

输出 #3

822243495

输入#4

7 6
3 2 4 1 0 5 6

输出#4

36

注意

在第一个测试用例中,“abb”是唯一可能的解决方案。

在第二个测试用例中,可以很容易地表明不存在可能的字符串,因为所有字母都必须相等。

在第四个测试用例中,一个可能的字符串是“ddbacef”。

请记住以 $$$998244353$$$ 为模打印出你的答案。