分数: 466 分
问题陈述
高桥宿 N 球编号为 1 to N 进入一些 M 盒子编号为 1 to M,按球的顺序 1, 球 2, \dots, 球 N。每个盒子可以容纳任意数量的球。让 B_i 表示该球所在的盒子编号 i 被放置 (1 \leq B_i \leq M).
青木记录了盒子编号序列 B_1, B_2, \dots, B_N 将其转换为“压缩数字序列” C_1, C_2, \dots, C_N 使用以下过程。此过程分配新号码 1, 2, 3, \dots 按照每个盒子编号第一次出现的顺序。
> 最初,没有分配给任何邮箱号码的压缩号码。
>
> 对于 i = 1, 2, \dots, N 按顺序执行以下操作:
> - 如果箱号 B_i 尚未分配压缩号码(即, B_i 不同于所有 B_1, B_2, \dots, B_{i-1}), 分配给箱号 B_i 尚未分配给任何盒子编号的最小正整数作为其压缩编号。套装 C_i 到那个压缩号码。
> - 如果箱号 B_i 已经被分配了一个压缩号码(即,其中存在一些元素 B_1, B_2, \dots, B_{i-1} 等于 B_i),设置 C_i 到已分配给箱号的压缩号 B_i.
例如,当箱号顺序为 (5, 5, 2, 7, 2),箱号 5 被分配压缩号码 1,箱号 2 被分配压缩号码 2和箱号 7 被分配压缩号码 3,产生压缩的数字序列 (1, 1, 2, 3, 2).
但是,部分记录变得脏且不可读。
给你一个序列 D_1, D_2, \dots, D_N 长度 N。当 D_i = 0的值 C_i 未知。当 D_i \neq 0,它必须保持 C_i = D_i.
求盒子编号序列的个数 B_1, B_2, \dots, B_N (其中每个 B_i 是介于 1 和 M 包括)使得压缩数序列 通过上述程序得到的 C_1, C_2, \dots, C_N 满足以下所有条件 D,模数 998244353。在这里,如果存在某些情况,则两个盒子编号序列被认为是不同的 i 这样他们的价值 B_i 不同。如果不存在有效的箱号序列,则输出 0.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- N \times \min(N, M) \leq 2.5 \times 10^7
- 0 \leq D_i \leq N
- 所有输入值均为整数。
输入
N M D_1 D_2 \dots D_N
- 第一行包含球的数量 N 和最大箱数 M,用空格分隔。
- 第二行包含 D_1, D_2, \dots, D_N,表示部分未知的压缩数字序列,以空格分隔。
- 当 D_i = 0,这意味着 i第一个压缩号码未知。
- 当 D_i \geq 1,这意味着 i第一个压缩数是 D_i.
输出
输出有效盒子编号序列的模数 998244353 在一行中。
样本输入 1
5 4 1 1 2 0 2
示例输出 1
48
示例输入 2
4 2 1 2 3 0
示例输出 2
0
示例输入 3
10 6 1 0 2 0 2 3 0 1 4 0
示例输出 3
51840
示例输入 4
24 15 1 0 2 0 3 0 1 4 0 2 5 0 0 3 6 0 4 0 6 7 0 5 0 7
示例输出 4
280519446
示例输入 5
1 1 0
示例输出 5
1