/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
整数 N と (1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます。
(1,2,\ldots,N) の順列 Q=(Q_1,Q_2,\ldots,Q_N) に対して、以下の操作をちょうど 1 回行うことにより得られる順列の中で辞書順最小の順列を Q'=(Q_1',Q_2',\ldots,Q_N') とします：
- 1\le l\le r\le N を満たす整数の組 (l,r) を選び、Q_l,Q_{l+1},\ldots,Q_r を反転させる。より厳密には、Q を (Q_1,Q_2,\ldots,Q_{l-1} , Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N) で置き換える。
Q'=P となる (1,2,\ldots,N) の順列 Q の個数を 998244353 で割ったあまりを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T
- 1\le N\le 5\times 10^5
- P は (1,2,\ldots,N) の順列
- 全てのテストケースにおける N の総和は 5\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N P_1 P_2 \ldots P_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
4 3 1 3 2 1 1 4 4 3 2 1 6 1 2 6 4 5 3
出力例 1
2 1 0 9
1 番目のテストケースについて考えます。
例えば Q=(2,3,1) の場合、(l,r)=(1,3) を選ぶことで (1,3,2) が得られます。(1,3,2) より辞書順で小さい順列は得られないので、Q'=(1,3,2) となります。したがって、Q=(2,3,1) は Q'=P を満たします。
Q'=P となる Q は Q=(2,3,1),(3,1,2) の 2 個です。
Score : 400 points
Problem Statement
You are given an integer N and a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).
For a permutation Q=(Q_1,Q_2,\ldots,Q_N) of (1,2,\ldots,N), let Q'=(Q_1',Q_2',\ldots,Q_N') be the lexicographically smallest permutation obtainable by performing the following operation exactly once:
- Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and reverse Q_l,Q_{l+1},\ldots,Q_r. More precisely, replace Q with (Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N).
Find the number, modulo 998244353, of permutations Q of (1,2,\ldots,N) such that Q'=P.
You are given T test cases; solve each of them.
Constraints
- 1\le T
- 1\le N\le 5\times 10^5
- P is a permutation of (1,2,\ldots,N).
- The sum of N over all test cases is at most 5\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N P_1 P_2 \ldots P_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
4 3 1 3 2 1 1 4 4 3 2 1 6 1 2 6 4 5 3
Sample Output 1
2 1 0 9
Consider the first test case.
For example, when Q=(2,3,1), choosing (l,r)=(1,3) gives (1,3,2). No permutation lexicographically smaller than (1,3,2) can be obtained, so we have Q'=(1,3,2). Thus, Q=(2,3,1) satisfies Q'=P.
There are two permutations Q such that Q'=P: Q=(2,3,1),(3,1,2).