The 67th Iteration of "Counting is Fun"
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
Macaque 把你带到了他的栖息地,向你展示了他的工作,甚至还强迫你替他做作业。虽然这对你来说可能并不容易,但 Macaque 已经渐渐喜欢上了你,甚至可能对你心存感激。然而,一切尚未结束,因为 Macaque 还必须解决他迄今为止最困难的问题。解决这个问题事关生死,决定了 Macaque 能否最终悟道并在管风琴阁楼中隐居度过余生。祝你好运。
给定两个整数 和 ,以及一个长度为 的数组 ()。保证 到 的每个整数都在 中至少出现一次。
一组 个人排成一排,站在编号为 的固定位置上。他们都想坐下,但有些人因为社交尴尬无法立即坐下。
对于某个长度为 的任意数组 (),每个人 的社交尴尬程度为 。入座过程在离散时间单位 中进行,规则如下:
- 若 ,则第 个人在时刻 坐下。
- 否则(),第 个人在某个时间单位 的开始时坐下,当且仅当以下两个条件同时满足:
- 在时刻 之前已有至少 个人坐下。
- 他的至少一个邻居(第 或第 个人,若存在)已在时刻 之前坐下。
在每个时间单位开始时,每个站着的人检查这些条件。所有满足条件的人同时坐下,然后过程进入下一个时间单位。
对于每个 , 表示第 个人坐下的时间单位。你的任务是确定有多少个不同的数组 与给定的数组 一致。由于这个数可能很大,请对 取模。
请注意本题使用的模数不同寻常,且 是素数。
输入格式
第一行包含一个整数 ()— 测试用例的数量。
每个测试用例的描述如下:
- 第一行包含两个整数 和 ()— 人数和过程的总时长。
- 第二行包含 个整数 (),其中 是第 个人坐下的时间单位。
保证所有测试用例的 之和不超过 。保证给定的每个数组 包含 到 的所有整数。
输出格式
对于每个测试用例,输出一个整数 — 能产生给定数组 的不同数组 的数量,对 取模。
样例
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
说明
在第一个测试用例中,仅有的 个合法数组是 和 。在时刻 ,第 个人和第 个人坐下。然后第 个人在时刻 坐下。如果 为 ,第 个人会在时刻 就坐下;如果 大于 ,第 个人将无法在时刻 坐下,因为在时刻 之前只有 个人坐下。可以证明 唯一可能的值是 。
在第二个测试用例中,不存在合法数组,因为第 个人不可能在其任一邻居之前坐下。
来源
导入自 Codeforces — Codeforces Round 1090 (Div. 4)。
Codeforces Round 1090 (Div. 4)
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 7
- 开始于
- 2026-11-11 15:00
- 结束于
- 2026-11-11 17:30
- 持续时间
- 2.5 小时
- 主持人
- 参赛人数
- 14