A7415 | $小枫的密码锁$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小枫、小午和小安三个人在玩一个解密游戏。 小枫设计了一个特殊的密码锁，锁上有 $M$ 个数字按键，编号为 $1$ 到 $M$。 密码是一个长度为 $N$ 的序列，每个位置可以是 $1$ 到 $M$ 中的任意数字。 小枫还设定了一个约束规则，用长度为 $M$ 的数组 $X = (X_1, X_2, \dots, X_M)$ 表示。 规则是：对于每个数字 $B$（$1 \leq B \leq M$），在密码序列中，任意两次出现 $B$ 之间（包括这两次出现的位置），都必须至少出现一次 $X_B$。 换句话说，如果密码中有两个位置 $l < r$ 都等于 $B$，那么在区间 $[l, r]$ 内，必须至少有一个位置的值是 $X_B$。 小午需要猜出所有可能的密码。小安负责统计一共有多少种不同的密码满足这个约束。 请你帮小安算出这个数量，并对 $998244353$ 取模。

第一行两个整数 $M$ 和 $N$。 第二行 $M$ 个整数 $X_1, X_2, \dots, X_M$，每个 $X_i$ 满足 $1 \leq X_i \leq M$。

输出一个整数，表示满足条件的密码个数，对 $998244353$ 取模。

输入 #1

3 4
2 1 2

输出 #1

C++ 编辑器

输入

输出