A16647 | $The Ancient Wizards' Capes$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

有 $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$ 取模。

每组测试包含多组用例。第一行为测试用例个数 $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$。

对于每组测试用例，输出一个整数，表示满足条件的斗篷安排方案数，对 $676\,767\,677$ 取模。

输入 #1

输出 #1

C++ 编辑器

输入

输出