A16647. The Ancient Wizards' Capes
编程题
普及/提高-
知识点
题目描述
有 $n$ 位巫师排成一行，从左到右编号为 $1$ 到 $n$。每位巫师都有一件隐形斗篷，可以披在他的左侧或右侧。Harry 从巫师 $1$ 的位置走到巫师 $n$ 的位置（$1 \le n \le 10^5$），并记录下他在每个巫师位置能看到多少巫师。对于每个位置 $i$，若巫师 $j$ 满足以下条件，则 $j$ 能被看到：
- 若巫师 $j$ 披在左侧，则 $i \geq j$。
- 若巫师 $j$ 披在右侧，则 $i \leq j$。
特别地，巫师 $i$ 总能被自己在第 $i$ 个位置看到。
Harry 的记录很古老，但在经过大量努力后你终于破译了这些数据。记录以长度为 $n$ 的数组 $a$ 给出，$a_i$（$1 \leq a_i \leq n$）表示 Harry 在巫师 $i$ 位置能看到的巫师数量。
你的任务是，计算所有满足 Harry 记录的可能斗篷安排的方案数，结果对 $676\,767\,677$ 取模。
- 若巫师 $j$ 披在左侧，则 $i \geq j$。
- 若巫师 $j$ 披在右侧，则 $i \leq j$。
特别地，巫师 $i$ 总能被自己在第 $i$ 个位置看到。
Harry 的记录很古老，但在经过大量努力后你终于破译了这些数据。记录以长度为 $n$ 的数组 $a$ 给出，$a_i$（$1 \leq a_i \leq n$）表示 Harry 在巫师 $i$ 位置能看到的巫师数量。
你的任务是，计算所有满足 Harry 记录的可能斗篷安排的方案数，结果对 $676\,767\,677$ 取模。
输入格式
每组测试包含多组用例。第一行为测试用例个数 $t$（$1 \leq t \leq 10^4$）。每组测试用例：
第一行是一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $a$ 的长度。
第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示 Harry 的记录。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
第一行是一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $a$ 的长度。
第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示 Harry 的记录。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
输出格式
对于每组测试用例，输出一个整数，表示满足条件的斗篷安排方案数，对 $676\,767\,677$ 取模。
输入输出样例
输入 #1
7 1 1 4 4 4 3 2 3 1 3 2 2 2 1 3 2 2 2 3 3 2 3 3 3 2 2
输出 #1
2 1 0 1 2 0 0
说明/提示
下面的图片展示了在第二组测试用例中满足 Harry 记录的一种斗篷安排方式。
巫师 1 的斗篷披在左侧，巫师 2、3、4 的斗篷披在右侧。
- 位置 1 能看到巫师 1、2、3、4。
- 位置 2 能看到巫师 1、2、3、4。
- 位置 3 能看到巫师 1、3、4。
- 位置 4 能看到巫师 1、4。
因此 Harry 的记录为 $[4, 4, 3, 2]$。可以证明这是唯一可能的安排。
第三组测试用例中，可以证明没有任何一种斗篷安排能得到该记录。
第五组测试用例中，有两种斗篷安排符合 Harry 的记录：
- $1 \mid \quad \mid 2 \quad 3 \, \mid$
- $\mid \, 1 \quad 2 \mid \quad \mid 3$
巫师 1 的斗篷披在左侧，巫师 2、3、4 的斗篷披在右侧。
- 位置 1 能看到巫师 1、2、3、4。
- 位置 2 能看到巫师 1、2、3、4。
- 位置 3 能看到巫师 1、3、4。
- 位置 4 能看到巫师 1、4。
因此 Harry 的记录为 $[4, 4, 3, 2]$。可以证明这是唯一可能的安排。
第三组测试用例中，可以证明没有任何一种斗篷安排能得到该记录。
第五组测试用例中，有两种斗篷安排符合 Harry 的记录：
- $1 \mid \quad \mid 2 \quad 3 \, \mid$
- $\mid \, 1 \quad 2 \mid \quad \mid 3$