/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
数列 (1,2,\dots,n) に対して、以下の操作をちょうど m 回繰り返したところ、(a_1,\dots ,a_n) になりました。
- 項を 1 つ選んで消す。その後、消した項を数列の先頭か末尾に付け加える。
m 回の操作列としてありうるものの数を 998244353 で割ったあまりを求めてください。
ただし、2 つの操作列が同じであるとは、「どの操作についても、選んだ項と付け加えた位置がどちらも等しいこと」とします。
制約
- 2\le n \le 3000
- 1\le m \le 3000
- a_1,\dots ,a_n は 1,\dots,n の順列
入力
入力は以下の形式で標準入力から与えられる。
n m a_1 \dots a_n
出力
操作列としてありうるものの数を 998244353 で割ったあまりを出力せよ。
入力例 1
5 2 1 2 4 5 3
出力例 1
5
以下の 5 通りの操作列がありえます。
- 1 を消して先頭に付け加える。数列は (1,2,3,4,5) となる。その後、3 を消して末尾に付け加える。数列は (1,2,4,5,3) となる。
- 3 を消して先頭に付け加える。数列は (3,1,2,4,5) となる。その後、3 を消して末尾に付け加える。数列は (1,2,4,5,3) となる。
- 3 を消して末尾に付け加える。数列は (1,2,4,5,3) となる。その後、1 を消して先頭に付け加える。数列は (1,2,4,5,3) となる。
- 3 を消して末尾に付け加える。数列は (1,2,4,5,3) となる。その後、3 を消して末尾に付け加える。数列は (1,2,4,5,3) となる。
- 5 を消して末尾に付け加える。数列は (1,2,3,4,5) となる。その後、3 を消して末尾に付け加える。数列は (1,2,4,5,3) となる。
入力例 2
2 16 1 2
出力例 2
150994942
4 種類の操作のうち、2 種類では数列が全く変わらず、もう 2 種類では 2 項が入れ替わります。 このことから、全ての操作列のうち半分である 4^m/2 = 2^{31} = 2147483648 が求める操作列の数であることが示せます。 よって、2147483648 を 998244353 で割ったあまりである 150994942 が答えです。
入力例 3
10 3000 3 7 10 1 9 5 4 8 6 2
出力例 3
129989699
Score : 700 points
Problem Statement
We applied the following operation m times on the sequence (1,2,\dots,n), and it resulted in (a_1,\dots ,a_n).
- Erase one element. Then, add the erased element to the beginning or end of the sequence.
Find the number of possible sequences of the m operations, modulo 998244353.
Here, two sequences of operations are considered the same when, in every operation, the same element is chosen and added to the same position.
Constraints
- 2\le n \le 3000
- 1\le m \le 3000
- a_1,\dots ,a_n is a permutation of 1,\dots,n.
Input
Input is given from Standard Input in the following format:
n m a_1 \dots a_n
Output
Print the number of possible sequences of the m operations, modulo 998244353.
Sample Input 1
5 2 1 2 4 5 3
Sample Output 1
5
There are five possible sequences of operations, as follows:
- Erase 1 and add it to the beginning, which results in (1,2,3,4,5). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
- Erase 3 and add it to the beginning, which results in (3,1,2,4,5). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
- Erase 3 and add it to the end, which results in (1,2,4,5,3). Then, erase 1 and add it to the beginning, which results in (1,2,4,5,3).
- Erase 3 and add it to the end, which results in (1,2,4,5,3). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
- Erase 5 and add it to the end, which results in (1,2,3,4,5). Then, erase 3 and add it to the end, which results in (1,2,4,5,3).
Sample Input 2
2 16 1 2
Sample Output 2
150994942
Two of the four kinds of operations have no effect on the sequence, and the other two swap the two elements. From this fact, we can show that there are 4^m/2 = 2^{31} = 2147483648 sequences of operations - half of all possible sequences - that we want to count. Thus, the answer is 2147483648 modulo 998244353, that is, 150994942.
Sample Input 3
10 3000 3 7 10 1 9 5 4 8 6 2
Sample Output 3
129989699