← 返回题目列表

Codeforces · 2218/G

G. 《计数很有趣》第 67 次迭代

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

猕猴带你去了他的栖息地,向你展示了他的工作,甚至强迫你为他做作业。虽然这对你来说可能并不容易,但猕猴已经开始喜欢你,甚至可能对你心存感激。然而,一切还没有结束,猕猴还需要解决他迄今为止最困难的问题。解决这个问题是生死攸关的问题,它决定了猕猴能否最终获得启蒙,并在风琴阁楼中隐居,度过永恒的余生。祝你好运。

给定两个整数 $$$n$$$ 和 $$$m$$$,以及一个长度为 $$$n$$$ 的数组 $$$b$$$ ($$$0 \le b_i \lt m$$$)。保证从 $$$0$$$ 到 $$$m-1$$$ 的每个整数在 $$$b$$$ 中至少出现一次。

一群 $$$n$$$ 人排成一排,固定位置编号为 $$$1、2、\dots、n$$$。他们都想坐下来,但有些人在社交上太尴尬,无法立即坐下。

对于长度为 $$$n$$$ ($$$0 \le a_i \lt n$$$) 的任意数组 $$$a$$$,每个人 $$$i$$$ 都有一个社交尴尬级别 $$$a_i$$$。考虑一下演变中的座位过程 离散时间单位 $$$0, 1, 2, \dots$$$ 如下:

  • 如果$$$a_i = 0$$$,人$$$i$$$将在$$$0$$$时间坐下。
  • 否则 ($$$a_i \gt 0$$$),人 $$$i$$$ 将在时间单位 $$$t$$$ 的开始处坐下,如果 两者 满足以下条件的 :
    1. 至少$$$a_i$$$人已经坐下 严格之前 时间$$$t$$$。
    2. 至少一个邻居($$$i - 1$$$ 或 $$$i + 1$$$,如果存在)已经坐下 严格之前 时间$$$t$$$。

在每个时间单位开始时,每个站立的人都会检查这些条件。所有符合条件的人都坐下 同时,然后过程前进到下一个时间单位。

对于每个 $$$i$$$,值 $$$b_i$$$ 表示人 $$$i$$$ 坐下的时间单位。你的任务是确定 有多少个不同的数组$$$a$$$ 与给定数组 $$$b$$$ 一致。由于这个数字可能非常大,因此输出它对 $$${\color{red}{676767677}}$$$ 取模。

请注意,此问题使用了不寻常的模数,$$$676767677$$$ 是素数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的描述如下:

  • 第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m \le n \le 2 \cdot 10^5$$$) — 人数和过程的总持续时间。
  • 第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \lt m$$$),其中 $$$b_i$$$ 是人 $$$i$$$ 坐下的时间单位。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。保证每个提供的数组 $$$b$$$ 包含从 $$$0$$$ 到 $$$m-1$$$ 的每个整数。

输出

对于每个测试用例,输出一个整数 - 产生给定数组 $$$b$$$ 的不同数组 $$$a$$$ 的数量,以 $$${\color{red}{676767677}}$$$ 为模。

示例

输入
复制

7
4 3
0 1 2 0
8 4
0 1 2 3 1 2 0 1
9 5
1 0 1 3 4 3 2 1 0
15 14
3 0 1 2 3 4 5 6 7 8 9 10 11 12 13
5 5
4 3 0 1 2
5 2
0 1 1 1 0
3 2
0 1 1

输出
复制

2
0
1920
138007136
8
0
0

注意

在第一个测试用例中,唯一的 2 个有效数组是 $$$[0, 1, 3, 0]$$$ 和 $$$[0, 2, 3, 0]$$$。在 $$$0$$$ 时刻,第 $$$1$$$ 和第 $$$4$$$ 人坐下。然后$$$2$$$ 在时间$$$1$$$ 坐下。如果 $$$a_2$$$ 是 $$$0$$$,人 $$$2$$$ 就会在 $$$0$$$ 时间坐下,而如果 $$$a_2$$$ 大于 $$$2$$$,人 $$$2$$$ 将无法在 $$$1$$$ 时间坐下,因为只有 $$$2$$$ 人在时间 $$$1$$$ 之前坐下。可以证明,$$$a_3$$$ 的唯一可能值是$$$3$$$。

在第二个测试用例中,没有有效的数组,因为 $$$5$$$ 不可能在任何一个邻居之前坐下。