/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
(1, 2, \ldots, N) の順列 P = (P_1, P_2, \ldots, P_N) が与えられます。
下記の 2 つの条件をともに満たす長さ N の整数列 A = (A_1, A_2, \ldots, A_N) の個数を 998244353 で割ったあまりを出力してください。
- すべての i = 1, 2, \ldots, N について、1 \leq A_i \leq M。
- 整数列 A は整数列 (A_{P_1}, A_{P_2}, \ldots, A_{P_N}) より辞書順で小さい。
辞書順で小さいとは？
整数列 X = (X_1, X_2, \ldots, X_N) が 整数列 Y = (Y_1, Y_2, \ldots, Y_N) より辞書順で小さいとは、下記の 2 つの条件をともに満たす整数 1 \leq i \leq N が存在することを言います。
- 1 \leq j \leq i-1 を満たすすべての整数 j について、X_j = Y_j
- X_i \lt Y_i
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq P_i \leq N
- i \neq j \implies P_i \neq P_j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M P_1 P_2 \ldots P_N
出力
問題文中の 2 つの条件をともに満たす整数列 A の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
4 2 4 1 3 2
出力例 1
6
問題文中の 2 つの条件をともに満たす整数列 A は、
(1, 1, 1, 2), (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 2), (2, 1, 1, 2), (2, 1, 2, 2) の 6 個です。
例えば、A = (1, 1, 1, 2) のとき、(A_{P_1}, A_{P_2}, A_{P_3}, A_{P_4}) = (2, 1, 1, 1) であり、これは A より辞書順で大きいです。
入力例 2
1 1 1
出力例 2
0
入力例 3
20 100000 11 15 3 20 17 6 1 9 5 19 10 16 7 8 12 2 18 14 4 13
出力例 3
55365742
Score : 500 points
Problem Statement
You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N).
Print the number of integer sequences A = (A_1, A_2, \ldots, A_N) of length N that satisfy both of the conditions below, modulo 998244353.
- 1 \leq A_i \leq M for every i = 1, 2, \ldots, N.
- The integer sequence A is lexicographically smaller than the integer sequence (A_{P_1}, A_{P_2}, \ldots, A_{P_N}).
What is lexicographical order?
An integer sequence X = (X_1,X_2,\ldots,X_N) is lexicographically smaller than an integer sequence Y = (Y_1,Y_2,\ldots,Y_N) when there is an integer 1 \leq i \leq N that satisfies both of the conditions below.
- For all integers j (1 \leq j \leq i-1), X_j=Y_j.
- X_i < Y_i
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq P_i \leq N
- i \neq j \implies P_i \neq P_j
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M P_1 P_2 \ldots P_N
Output
Print the number of integer sequences A of length N that satisfy both of the conditions in the Problem Statement, modulo 998244353.
Sample Input 1
4 2 4 1 3 2
Sample Output 1
6
Six integer sequences A satisfy both of the conditions: (1, 1, 1, 2), (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 2), (2, 1, 1, 2), and (2, 1, 2, 2).
For instance, when A = (1, 1, 1, 2), we have (A_{P_1}, A_{P_2}, A_{P_3}, A_{P_4}) = (2, 1, 1, 1), which is lexicographically larger than A.
Sample Input 2
1 1 1
Sample Output 2
0
Sample Input 3
20 100000 11 15 3 20 17 6 1 9 5 19 10 16 7 8 12 2 18 14 4 13
Sample Output 3
55365742