← 返回题目列表

AtCoder · arc186_e

E. 缺少子序列

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

分数: 1000 点

问题陈述

给定一个整数序列 (X_1,\dots,X_M) 长度 M 组成 1,\dots,K.

查找序列数 (A_1,\dots,A_N) 长度 N 组成 1,\dots,K 满足以下条件,模 998244353:

  • 在所有长度序列中 M 组成 1,\dots,K,唯一不能作为(不一定是连续的)子序列获得的序列 (A_1,\dots,A_N) is (X_1,\dots,X_M).

约束

  • 2\le M,K \le N \le 400
  • 1\le X_i \le K
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M K
X_1 X_2 \dots X_M

输出

打印满足条件的序列数,模 998244353.


示例输入 1

5 2 3
1 1

示例输出 1

4

以下四个序列满足条件:

  • (2, 3, 1, 2, 3)
  • (2, 3, 1, 3, 2)
  • (3, 2, 1, 2, 3)
  • (3, 2, 1, 3, 2)

示例输入 2

400 3 9
1 8 6

示例输出 2

417833302

示例输入 3

29 3 10
3 3 3

示例输出 3

495293602

示例输入 4

29 3 10
3 3 4

示例输出 4

0