← 返回题目列表

AtCoder · awc0044_e

E. 压缩数列的恢复

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

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