/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正整数 N, M, K が与えられます．正整数列 A = (A_0, \ldots, A_{N-1}) に対する次の操作を考えます．
- k=0, 1, \ldots, K-1 の順に次を行う．
- A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N} を昇順にソートする．つまり A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N} を小さい方から順に並べたものを (x_0, \ldots, x_{M-1}) とするとき，各 0\leq j < M に対して A_{(k+j)\bmod N} を x_j に置き換える．
1 以上 N 以下の整数からなる順列 B = (B_0, \ldots, B_{N-1}) が与えられます．正整数列 A であって，上記の操作を行った結果が B と一致するものの個数を 998244353 で割った余りを答えてください．
制約
- 2\leq N\leq 3\times 10^5
- 2\leq M\leq N
- 1\leq K\leq 10^9
- 1\leq B_i\leq N
- i\neq j ならば B_i\neq B_j
入力
入力は以下の形式で標準入力から与えられます．
N M K
B_0 \ldots B_{N-1}
出力
正整数列 A であって，操作を行った結果が B と一致するものの個数を 998244353 で割った余りを出力してください．
入力例 1
6 3 5 6 4 2 3 1 5
出力例 1
18
例えば A = (4,1,5,6,2,3) が条件を満たします．この A に対して，操作は次のように進行します．
- k=0 に対する操作により，A は (1,4,5,6,2,3) になる．
- k=1 に対する操作により，A は (1,4,5,6,2,3) になる．
- k=2 に対する操作により，A は (1,4,2,5,6,3) になる．
- k=3 に対する操作により，A は (1,4,2,3,5,6) になる．
- k=4 に対する操作により，A は (6,4,2,3,1,5) になり，B に一致する．
入力例 2
6 3 5 6 5 4 3 2 1
出力例 2
0
条件を満たす A は存在しません．
入力例 3
20 20 149 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12
出力例 3
401576539
1 以上 20 以下の整数からなる順列がすべて条件を満たします．
Score : 700 points
Problem Statement
You are given positive integers N, M, and K. Consider the following operation on a sequence of positive integers A = (A_0, \ldots, A_{N-1}).
- Do the following for k=0, 1, \ldots, K-1 in this order.
- Sort A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N} in ascending order. That is, replace A_{(k+j)\bmod N} with x_j for each 0\leq j < M, where (x_0, \ldots, x_{M-1}) is the result of sorting A_{k\bmod N}, A_{(k+1)\bmod N}, \ldots, A_{(k+M-1)\bmod N} in ascending order.
You are given a permutation B = (B_0, \ldots, B_{N-1}) of the integers from 1 through N. Find the number of sequences A of positive integers that will equal B after performing the operation above, modulo 998244353.
Constraints
- 2\leq N\leq 3\times 10^5
- 2\leq M\leq N
- 1\leq K\leq 10^9
- 1\leq B_i\leq N
- B_i\neq B_j if i\neq j.
Input
The input is given from Standard Input in the following format:
N M K
B_0 \ldots B_{N-1}
Print the number of sequences A of positive integers that will equal B after performing the operation, modulo 998244353.
Sample Input 1
6 3 5 6 4 2 3 1 5
Sample Output 1
18
For instance, A = (4,1,5,6,2,3) satisfies the condition. On this A, the operation will proceed as follows.
- The action for k=0 changes A to (1,4,5,6,2,3).
- The action for k=1 changes A to (1,4,5,6,2,3).
- The action for k=2 changes A to (1,4,2,5,6,3).
- The action for k=3 changes A to (1,4,2,3,5,6).
- The action for k=4 changes A to (6,4,2,3,1,5), which equals B.
Sample Input 2
6 3 5 6 5 4 3 2 1
Sample Output 2
0
No sequence A satisfies the condition.
Sample Input 3
20 20 149 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output 3
401576539
All permutations of the integers from 1 through 20 satisfy the condition.