/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
人 1, 人 2, \dots, 人 N の N 人の人がいて、前から (1,2,\dots,N) の順に一列に並んでいます。人 i は色 c_i の服を着ています。
高橋君は任意の 2 人 i,j を選んで人 i と人 j の位置を入れ替える操作を K 回繰り返しました。
K 回の操作を終了した時点で、1 \leq i \leq N を満たすすべての整数 i に対して、前から i 番目の人が着ている服の色は c_i と一致しました。
K 回の操作を終了した後にあり得る人の並び方は何通りありますか？ 答えを 998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 200000
- 1 \leq K \leq 10^9
- 1 \leq c_i \leq N
- 入力される値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K c_1 c_2 \dots c_N
出力
答えを出力せよ。
入力例 1
4 1 1 1 2 1
出力例 1
3
高橋君の操作、および操作後の列としてあり得るものをすべて挙げると次のようになります。
- 人 1 と人 2 の位置を入れ替える。操作後の並び方は (2, 1, 3, 4) となる。
- 人 1 と人 4 の位置を入れ替える。操作後の並び方は (4, 2, 3, 1) となる。
- 人 2 と人 4 の位置を入れ替える。操作後の並び方は (1, 4, 3, 2) となる。
入力例 2
3 3 1 1 2
出力例 2
1
あり得る高橋君の操作の例を 1 つ挙げると次のようになります。
- 1 回目の操作で人 1 と人 3 の位置を入れ替える。操作後の並び方は (3, 2, 1) となる。
2 回目の操作で人 2 と人 3 の位置を入れ替える。操作後の並び方は (2, 3, 1) となる。
3 回目の操作で人 1 と人 3 の位置を入れ替える。操作後の並び方は (2, 1, 3) となる。
操作の途中においては、前から i 番目の人の服の色が c_i と必ずしも一致しなくてもよいのに注意してください。
入力例 3
10 4 2 7 1 8 2 8 1 8 2 8
出力例 3
132
Score : 600 points
Problem Statement
There are N people called Person 1, Person 2, \dots, Person N, lined up in a row in the order of (1,2,\dots,N) from the front. Person i is wearing Color c_i.
Takahashi repeated the following operation K times: choose two People i and j arbitrarily and swap the positions of Person i and Person j.
After the K operations have ended, the color that the i-th person from the front is wearing coincided with c_i, for every integer i such that 1 \leq i \leq N.
How many possible permutations of people after the K operations are there? Find the count modulo 998244353.
Constraints
- 2 \leq N \leq 200000
- 1 \leq K \leq 10^9
- 1 \leq c_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K c_1 c_2 \dots c_N
Output
Print the answer.
Sample Input 1
4 1 1 1 2 1
Sample Output 1
3
Here is a comprehensive list of possible Takahashi's operations and permutations of people after each operation.
- Swap the positions of Person 1 and Person 2, resulting in a permutation (2, 1, 3, 4).
- Swap the positions of Person 1 and Person 4, resulting in a permutation (4, 2, 3, 1).
- Swap the positions of Person 2 and Person 4, resulting in a permutation (1, 4, 3, 2).
Sample Input 2
3 3 1 1 2
Sample Output 2
1
Here is an example of a possible sequence of Takahashi's operations.
- In the 1-st operation, he swaps the positions of Person 1 and Person 3, resulting in a permutation (3, 2, 1).
In the 2-nd operation, he swaps the positions of Person 2 and Person 3, resulting in a permutation (2, 3, 1).
In the 3-rd operation, he swaps the positions of Person 1 and Person 3, resulting in a permutation (2, 1, 3).
Note that, during the sequence of operations, the color that the i-th person from the front is wearing does not necessarily coincide with c_i.
Sample Input 3
10 4 2 7 1 8 2 8 1 8 2 8
Sample Output 3
132