← 返回题目列表

AtCoder · arc112_e

E. 雪茄盒

中文机器翻译题面 查看原题

分数: 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