CF2218G The 67th Iteration of "Counting is Fun"

猕猴已经带你参观了他的栖息地，向你展示了他的工作，甚至强迫你替他做作业。虽然这对你来说也许并不轻松，但猕猴开始喜欢你，甚至可能对你怀有一丝感激之情。然而，一切并未结束，因为猕猴还要解决他迄今为止最难的问题。解决这个问题对他来说关乎生死，也关系到他能否最终开悟并隐居在风琴阁余生。祝你好运。 你将得到两个整数 $n$ 和 $m$，以及一个长度为 $n$ 的数组 $b$（$0 \le b_i < m$）。保证 $b$ 中包含从 $0$ 到 $m-1$ 的每个整数至少一次。 有 $n$ 个人依次站成一排，固定在编号 $1, 2, \dots, n$ 的位置上。他们都想坐下，但有些人过于社恐，无法立刻坐下。 对于任意长度为 $n$ 的数组 $a$（$0 \le a_i < n$），每个人 $i$ 有一个社交尴尬度 $a_i$。考虑如下在离散时刻 $0, 1, 2, \dots$ 进行的入座过程： - 如果 $a_i = 0$，那么第 $i$ 个人将在时刻 $0$ 就坐下。 - 否则（$a_i > 0$），第 $i$ 个人仅当同时满足以下两个条件时，会在某时刻 $t$ 的开始坐下： 1. 在时刻 $t$ 之前，至少有 $a_i$ 个人已经坐下。 2. 他的邻居（第 $i-1$ 或 $i+1$ 个人，如果存在）中至少有一人在时刻 $t$ 之前已经坐下。 在每个时刻开始时，每个仍站着的人都会检查这些条件。所有满足条件的人会同时入座，然后进入下一个时刻。 对于每个 $i$，$b_i$ 表示第 $i$ 个人坐下的时刻。请你计算，能够得到给定 $b$ 数组的不同 $a$ 数组有多少个。由于结果可能很大，请对 $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 < m$），其中 $b_i$ 表示第 $i$ 个人坐下的时刻。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。保证每个给定的 $b$ 数组都包含 $0$ 到 $m-1$ 的所有整数各至少一次。

对于每个测试用例，输出一个整数，表示能产生给定 $b$ 数组的不同 $a$ 数组个数，对 $676767677$ 取模。

在第一个测试用例中，唯一的两组合法数组为 $[0, 1, 3, 0]$ 和 $[0, 2, 3, 0]$。在时刻 $0$，第 $1$ 和第 $4$ 个人坐下。接下来，第 $2$ 个人在时刻 $1$ 坐下。如果 $a_2 = 0$，第 $2$ 个人应当在时刻 $0$ 就坐下；若 $a_2 > 2$，则在时刻 $1$ 时，只有 $2$ 个人在 $1$ 之前坐下，则他无法坐下。所以 $a_3$ 只有 $3$ 是可能的。 在第二个测试用例中，没有合法方案，因为第 $5$ 个人不可能在邻居之前坐下。 由 ChatGPT 5 翻译