#CF2218G. The 67th Iteration of "Counting is Fun"

The 67th Iteration of "Counting is Fun"

题目描述

Macaque 把你带到了他的栖息地,向你展示了他的工作,甚至还强迫你替他做作业。虽然这对你来说可能并不容易,但 Macaque 已经渐渐喜欢上了你,甚至可能对你心存感激。然而,一切尚未结束,因为 Macaque 还必须解决他迄今为止最困难的问题。解决这个问题事关生死,决定了 Macaque 能否最终悟道并在管风琴阁楼中隐居度过余生。祝你好运。

给定两个整数 nn 和 mm,以及一个长度为 nn 的数组 bb(0≤bi<m0 \le b_i \lt m)。保证 00 到 m−1m-1 的每个整数都在 bb 中至少出现一次。

一组 nn 个人排成一排,站在编号为 1,2,…,n1, 2, \dots, n 的固定位置上。他们都想坐下,但有些人因为社交尴尬无法立即坐下。

对于某个长度为 nn 的任意数组 aa(0≤ai<n0 \le a_i \lt n),每个人 ii 的社交尴尬程度为 aia_i。入座过程在离散时间单位 0,1,2,…0, 1, 2, \dots 中进行,规则如下:

  • 若 ai=0a_i = 0,则第 ii 个人在时刻 00 坐下。
  • 否则(ai>0a_i \gt 0),第 ii 个人在某个时间单位 tt 的开始时坐下,当且仅当以下两个条件同时满足:
    1. 在时刻 tt 之前已有至少 aia_i 个人坐下。
    2. 他的至少一个邻居(第 i−1i - 1 或第 i+1i + 1 个人,若存在)已在时刻 tt 之前坐下。

在每个时间单位开始时,每个站着的人检查这些条件。所有满足条件的人同时坐下,然后过程进入下一个时间单位。

对于每个 ii,bib_i 表示第 ii 个人坐下的时间单位。你的任务是确定有多少个不同的数组 aa 与给定的数组 bb 一致。由于这个数可能很大,请对 676767677{\color{red}{676767677}} 取模。

请注意本题使用的模数不同寻常,且 676767677676767677 是素数。

输入格式

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

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

  • 第一行包含两个整数 nn 和 mm(1≤m≤n≤2⋅1051 \le m \le n \le 2 \cdot 10^5)— 人数和过程的总时长。
  • 第二行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n(0≤bi<m0 \le b_i \lt m),其中 bib_i 是第 ii 个人坐下的时间单位。

保证所有测试用例的 nn 之和不超过 2⋅1052 \cdot 10^5。保证给定的每个数组 bb 包含 00 到 m−1m-1 的所有整数。

输出格式

对于每个测试用例,输出一个整数 — 能产生给定数组 bb 的不同数组 aa 的数量,对 676767677{\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

说明

在第一个测试用例中,仅有的 22 个合法数组是 [0,1,3,0][0, 1, 3, 0] 和 [0,2,3,0][0, 2, 3, 0]。在时刻 00,第 11 个人和第 44 个人坐下。然后第 22 个人在时刻 11 坐下。如果 a2a_2 为 00,第 22 个人会在时刻 00 就坐下;如果 a2a_2 大于 22,第 22 个人将无法在时刻 11 坐下,因为在时刻 11 之前只有 22 个人坐下。可以证明 a3a_3 唯一可能的值是 33。

在第二个测试用例中,不存在合法数组,因为第 55 个人不可能在其任一邻居之前坐下。

来源

导入自 Codeforces — Codeforces Round 1090 (Div. 4)。