/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 700 点
問題文
整数 N,K と長さ K の整数列 A=(A_1,A_2,\ldots,A_K) が与えられます。A の各要素は 1 以上 N 以下で相異なることが保証されます。
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) に対して f(P) を以下のように定義します。
- P に対して以下の操作を行うことのできる回数の最大値。
- P_i < \max(P_1,P_2,\ldots,P_{i-1}) を満たす 2\le i\le N を選び、P_i を先頭に移動させる。つまり、P を (P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N) で置き換える。
i=1,2,\ldots,K に対し P_i=A_i を満たす (1,2,\ldots,N) の順列 P は (N-K)! 通りありますが、それら全てに対する f(P) の総和を 998244353 で割ったあまりを求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\le T\le 10^5
- 1\le K\le N
- 全てのテストケースにおける N の総和は 5\times 10^5 以下
- 1\le A_i\le N
- A の各要素は相異なる
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N K A_1 A_2 \ldots A_K
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
入力例 1
3 3 1 1 4 2 3 2 10 3 2 1 7
出力例 1
2 6 1382640
1 番目のテストケースについて考えます。
i=1,2,\ldots,K に対し P_i=A_i を満たす (1,2,\ldots,N) の順列 P は P=(1,2,3),(1,3,2) の 2 つです。
P=(1,2,3) のとき、操作を 1 回も行うことができないので f(P)=0 です。
P=(1,3,2) のとき、以下のようにすることで操作を 2 回行うことができます。
- i=3 を選ぶ。P=(2,1,3) となる。
- i=2 を選ぶ。P=(1,2,3) となる。
3 回以上操作することはできないので、この場合は f(P)=2 です。
以上より、求める答えは 0+2=2 となります。
Score : 700 points
Problem Statement
You are given integers N,K and an integer sequence A=(A_1,A_2,\ldots,A_K) of length K. It is guaranteed that each element of A is between 1 and N, inclusive, and all elements are distinct.
For a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N), define f(P) as follows.
- The maximum number of times the following operation can be performed on P.
- Choose 2\le i\le N satisfying P_i < \max(P_1,P_2,\ldots,P_{i-1}), and move P_i to the front. That is, replace P with (P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N).
There are (N-K)! permutations P of (1,2,\ldots,N) satisfying P_i=A_i for i=1,2,\ldots,K. Find the sum, modulo 998244353, of f(P) over all such permutations.
You are given T test cases; solve each of them.
Constraints
- 1\le T\le 10^5
- 1\le K\le N
- The sum of N over all test cases is at most 5\times 10^5.
- 1\le A_i\le N
- All elements of A are distinct.
- 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 K A_1 A_2 \ldots A_K
Output
Output the answer for the test cases in order, separated by newlines.
Sample Input 1
3 3 1 1 4 2 3 2 10 3 2 1 7
Sample Output 1
2 6 1382640
Consider the first test case.
The permutations P of (1,2,\ldots,N) satisfying P_i=A_i for i=1,2,\ldots,K are P=(1,2,3) and P=(1,3,2), giving two permutations.
When P=(1,2,3), no operation can be performed, so f(P)=0.
When P=(1,3,2), the operation can be performed twice as follows.
- Choose i=3. Now P=(2,1,3).
- Choose i=2. Now P=(1,2,3).
The operation cannot be performed three or more times, so f(P)=2 in this case.
Thus, the answer is 0+2=2.