Oolimry and Suffix Array
Contest: Codeforces Round 723 (Div. 2)
Difficulty rating: 2400
Tags: combinatorics, constructive algorithms, math

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$$$.

Input format:
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$$$.

Output format:
Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $$$998244353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 2
0 2 1

Example output:
1

Example input:
5 1
0 1 2 3 4

Example output:
0

Editorial:
First, let's consider a simpler problem.
Is it possible to make a string with a certain suffix array given an alphabet size $$$k$$$.
Consider two adjacent suffixes in the suffix array "xy" and "ab" where $$$b$$$ and $$$y$$$ are some strings and $$$x$$$ and $$$a$$$ are some characters i.e. $$$x$$$ is the first character of that suffix and similarly for $$$a$$$. If $$$b$$$ and $$$y$$$ don't exist we consider them as $, i.e. smaller than everything. Also, "xy" comes before "ab".
Observation: If the position of $$$b$$$ is less than the position of $$$y$$$ in the suffix array, $$$x$$$ must be less than $$$a$$$.
This can be easily shown as "xy" must be lexicographically smaller than "ab". This is sufficient also.
Thus we can iterate through the suffix array and check if $$$pos[arr[i]+1]>pos[arr[i+1]+1]$$$ where $$$arr$$$ is the suffix array and $$$pos$$$ is the position of the $$$i$$$th element in the suffix array. If this condition holds then the $$$arr[i]$$$ th character must be strictly less than the $$$arr[i+1]$$$ th character. Thus we can just count how many such pairs exist. If this count is larger than the alphabet size no such string is possible. Otherwise, such string exists. Note that special care must be taken when considering $$$arr[i]=n-1$$$ as $$$pos[n]$$$ may not be defined ($$$0$$$-indexed).
After tackling the simpler question we move on to the full question of counting how many such strings are there. If we consider the string as an array and the order of the array as the order of the suffix array meaning that the $$$i$$$ th element of this array is the $$$arr[i]$$$ th element of the string. We have now transformed the question into "Given that some elements must be greater than the previous elements while others can be equal. Count how many arrays are there such that the largest element is less than $$$k$$$". Consider the difference array, some elements must be $$$\geq 1$$$ while some can be 0. We add padding to the front and back of the array so as to account for the first value being non-zero and the last element being less than $$$k$$$. These two elements can both be 0. Let $$$cnt$$$ be the number of $$$\geq 1$$$ in the difference array. Now, this becomes count how many arrays of $$$(n-1+2)=(n+1)$$$ non-negative elements sum to $$$k-cnt$$$. This can be solved using stars and bars so the final answer comes out to be $$$n+1+k-cnt \choose n$$$ which can be found easily.
Final Complexity $$$O(n\log MOD)$$$ or $$$O(n)$$$ depending on how you find the modular inverse.
Btw $$$k$$$ was chosen to also be $$$\leq 2\times 10^5$$$ so as to hide the final complexity :)