分数: 700 点
问题陈述
我们应用了以下操作 序列上的 m 次 (1,2,\dots,n),结果是 (a_1,\dots ,a_n).
- 删除一个元素。然后,将删除的元素添加到序列的开头或结尾。
找出可能的序列数 m 运算,模数 998244353.
这里,当在每个操作中选择相同的元素并将其添加到相同的位置时,两个操作序列被认为是相同的。
约束
- 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
输出
打印可能的序列数 m 运算,模数 998244353.
示例输入 1
5 2 1 2 4 5 3
示例输出 1
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^m/2 = 2^{31} = 2147483648 操作序列 - 所有可能序列的一半 - 我们想要计数。 因此,答案是 2147483648 模数 998244353,即 150994942.
示例输入 3
10 3000 3 7 10 1 9 5 4 8 6 2
示例输出 3
129989699