AdditionalFile6997.zip

#6997. 「THUPC 2026 初赛」覆盖游戏

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

WCat 在玩一个覆盖游戏。

现在他有一个 $n \times n$ 的方格表，第 $i$ 行第 $j$ 列的格子编号为 $(i, j)$ 。这个方格表有 $n$个格为黑格，其余为白格，满足任意两个黑格既不同行也不同列。

对每个正整数 $k$ ，WCat 手上有无穷多个 $1 \times k$ 的红色矩形，也有无穷多个 $k \times 1$ 的蓝色矩形。WCat 需要用手上的这些矩形来覆盖方格表。

在这个填充游戏中，红色矩形只能横向放置，蓝色矩形只能纵向放置。更具体地说，对于一个 $1 \times k$ 的红色矩形，WCat 可以选择正整数 $i, j$ 满足 $1 \leq i, j+k-1 \leq n$ ，并用此红色矩形覆盖编号为 $(i, j+l), l=0,1, \ldots, k-1$ 的方格；对于一个 $k \times 1$ 的蓝色矩形，WCat 可以选择正整数 $i, j$ 满足 $1 \leq i+k-1, j \leq n$ ，并用此蓝色矩形覆盖编号为 $(i+l, j), l=0,1, \ldots, k-1$ 的方格。

WCat 需要用手上的这些矩形互不重叠地覆盖所有白格，同时不能覆盖到黑格。如果 WCat 用了 $2 n-2$ 个矩形，那么他就赢了这个游戏。

在两种覆盖方案中，两个矩形称为相同的，如果它们的颜色相同，且所覆盖的白格的编号集合相同；反之，两个矩形称为不同的。

WCat 想要知道他有多少种覆盖方案能够赢得这个覆盖游戏。两种覆盖方案不同，当且仅当存在一个白格，它在第一种覆盖方式中覆盖它的矩形与第二种覆盖方式中覆盖它的矩形不同。由于方案数可能很多，你只需要给出方案数对 $10^{9}+7$ 取模后得到的结果。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$ $\left(2 \leq n \leq 2 \times 10^{5}\right)$ ，表示方格表的边长。

第二行 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$ ，表示第 $i$ 列第 $a_{i}$ 行的格子为黑格。保证 $a_{1}, a_{2}, \ldots, a_{n}$为 $1,2, \ldots, n$ 的一个排列。

输出格式

输出到标准输出。

输出一行一个整数，表示能够赢得这个覆盖游戏的覆盖方案数，答案对 $10^{9}+7$ 取模。

样例 1

输入

2
1 2

输出

4

WCat 只能用 $1 \times 1$ 的矩形覆盖，而矩形可以是红色的或者蓝色的，故有 $2 \times 2=4$种覆盖方案。

样例 2

见题目目录下的 2.in 与 2.ans。

样例 3

见题目目录下的 3.in 与 3.ans。

样例 4

见题目目录下的 4.in 与 4.ans。

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。