Oolimry and Suffix Array

题意翻译

给定 $n$ 和 $k$ 和一个长度为 $n$ 的后缀数组 $s_0,s_1,\cdots,s_{n-1}$。 你需要求出当字符集 $\Sigma$ 的大小为 $k$ 时、有多少个长度为 $n$ 的字符串会产生这样的后缀数组，答案对 $998244353$ 取模。 $1\leq n,k\leq2\times10^5;0\leq s_i\leq n-1$ 且 $s_i$ 互不相同。 如果你不知道什么是后缀数组： 在本题中，假设 $s$ 为长度是 $n$ 的字符串，那么我们设第 $i$ 个 $s$ 的后缀为 $s[i\cdots n-1]$。将所有 $s$ 的后缀按照字典序排序，得到的字符串序列按顺序对应的编号组成的序列就是字符串 $s$ 的后缀数组。例如，对于字符串 $s=\texttt{"oolimry"}$，其后缀数组为 $[3,2,4,1,0,5,6]$，因为将其后缀排序后为 $[\texttt{imry,limry,mry,olimry,oolimry,ry,y}]$。 我们在本题中定义字符串 $a$ 比字符串 $b$ 的字典序小 $(a\not=b)$，仅当下列条件之一成立： - $a$ 是 $b$ 的前缀。 - 存在整数 $i$ 使得 $a_i<b_i$ 且对于任意整数 $j$ 使得 $1\leq j<i$，$a_j=b_j$ 成立。

题目描述

Once upon a time, Oolimry saw a suffix array. He wondered how many strings can produce this suffix array. More formally, given a suffix array of length $ n $ and having an alphabet size $ k $ , count the number of strings that produce such a suffix array. Let $ s $ be a string of length $ n $ . Then the $ i $ -th suffix of $ s $ is the substring $ s[i \ldots n-1] $ . A suffix array is the array of integers that represent the starting indexes of all the suffixes of a given string, after the suffixes are sorted in the lexicographic order. For example, the suffix array of oolimry is $ [3,2,4,1,0,5,6] $ as the array of sorted suffixes is $ [\texttt{imry},\texttt{limry},\texttt{mry},\texttt{olimry},\texttt{oolimry},\texttt{ry},\texttt{y}] $ . A string $ x $ is lexicographically smaller than string $ y $ , if either $ x $ is a prefix of $ y $ (and $ x\neq y $ ), or there exists such $ i $ that $ x_i < y_i $ , and for any $ 1\leq j < i $ , $ x_j = y_j $ .

输入输出格式

输入格式

The first line contain 2 integers $ n $ and $ k $ ( $ 1 \leq n \leq 200000,1 \leq k \leq 200000 $ ) — the length of the suffix array and the alphabet size respectively. The second line contains $ n $ integers $ s_0, s_1, s_2, \ldots, s_{n-1} $ ( $ 0 \leq s_i \leq n-1 $ ) where $ s_i $ is the $ i $ -th element of the suffix array i.e. the starting position of the $ i $ -th lexicographically smallest suffix. It is guaranteed that for all $ 0 \leq i< j \leq n-1 $ , $ s_i \neq s_j $ .

输出格式

Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $ 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

说明

In the first test case, "abb" is the only possible solution. In the second test case, it can be easily shown no possible strings exist as all the letters have to be equal. In the fourth test case, one possible string is "ddbacef". Please remember to print your answers modulo $ 998244353 $ .

题意翻译

给定 $n$ 和 $k$ 和一个长度为 $n$ 的后缀数组 $s_0,s_1,\cdots,s_{n-1}$。 你需要求出当字符集 $\Sigma$ 的大小为 $k$ 时、有多少个长度为 $n$ 的字符串会产生这样的后缀数组，答案对 $998244353$ 取模。 $1\leq n,k\leq2\times10^5;0\leq s_i\leq n-1$ 且 $s_i$ 互不相同。 如果你不知道什么是后缀数组： 在本题中，假设 $s$ 为长度是 $n$ 的字符串，那么我们设第 $i$ 个 $s$ 的后缀为 $s[i\cdots n-1]$。将所有 $s$ 的后缀按照字典序排序，得到的字符串序列按顺序对应的编号组成的序列就是字符串 $s$ 的后缀数组。例如，对于字符串 $s=\texttt{"oolimry"}$，其后缀数组为 $[3,2,4,1,0,5,6]$，因为将其后缀排序后为 $[\texttt{imry,limry,mry,olimry,oolimry,ry,y}]$。 我们在本题中定义字符串 $a$ 比字符串 $b$ 的字典序小 $(a\not=b)$，仅当下列条件之一成立： - $a$ 是 $b$ 的前缀。 - 存在整数 $i$ 使得 $a_i<b_i$ 且对于任意整数 $j$ 使得 $1\leq j<i$，$a_j=b_j$ 成立。