AdditionalFile4102.zip

P9418 [POI 2021/2022 R1] Impreza krasnali

题目背景

译自 XXIX Olimpiada Informatyczna – I etap Impreza krasnali。

题目描述

有 $n$ 个人依次站成一排，每个人手上都有一个数字，这 $n$ 个数字形成一个排列。

每个人会二选一地报告他左边或右边的人手上的数字。注意第一个人与第 $n$ 个人并不相邻，所以第一个人总是会报告第二个人的数字，第 $n$ 个人总是会报告第 $n-1$ 个人的数字。

现在你得到了 $n$ 个人报告的数字，求出原先的排列有多少种可能。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个整数，表示每个人报告的数字。

输出格式

一行一个整数，你的答案模 $10^9+7$。

输入输出样例 #1

输入 #1

5
3 4 3 4 1

输出 #1

2

输入输出样例 #2

输入 #2

见附件

输出 #2

0

输入输出样例 #3

输入 #3

见附件

输出 #3

1

说明/提示

对于所有数据，$2\leq n\leq 100000$。

子任务编号	附加限制	分数
1	$n\leq 10$	12
2	$n\leq 20$	30
3	$n\leq 1000$
4		28

#4102. 「POI 2021/2022 R1」Impreza krasnali

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – I etap Impreza krasnali

小矮人又举办了一次派对。他们还是有 $n$ 个人，每个人都戴了一顶尖尖的帽子。每个人的帽子都是从 $n$ 顶不同高度的帽子中随机选择，帽子的高度从 $1$ 到 $n$ 各不相同。但这次他们都坐在一张长桌的同一边。

因为小矮人们对这次派对印象深刻，当地的画家决定把这个盛况画成一幅画。为此，他需要知道每个小矮人坐在桌子的哪个位置，以及他们戴的是什么样的帽子。小矮人们记得自己的位置，但是帽子是随机分配的，他们都不记得自己的帽子有多高。他们只能告诉画家，他们桌子上的一个邻居戴的帽子有多高。

请你帮助画家写一个程序，计算出符合小矮人们的回答的帽子排列的数量。你只需要输出对 $10^{9}+7$ 取模的结果。如果小矮人们他们的回答相互矛盾，那么正确的答案就是 $0$。

输入格式

输入的第一行是一个整数 $n\ (n \geq 2)$，表示小矮人的数量。

第二行是 $n$ 个整数 $h_{1}, h_{2}, \ldots, h_{n}\ (1 \leq h_{i} \leq n)$，表示每个小矮人的回答。从左数第 $i$ 个小矮人告诉画家：「我桌子上的一个邻居戴的帽子高度是 $h_{i}$」。

输出格式

输出一行一个整数，表示符合小矮人们的回答的帽子排列的数量。你的答案应该对 $10^{9}+7$ 取模。

样例 1

输入

5
3 4 3 4 1

输出

2

第一个小矮人描述的肯定是第二个小矮人的帽子（所以第二个小矮人的帽子是 $3$），第五个小矮人描述的肯定是第四个小矮人的帽子（所以第四个小矮人的帽子是 $1$）。另外，第二个和第四个小矮人都记得有一顶 $4$ 号的帽子，所以那肯定是第三个小矮人的帽子。剩下的就是两种可能的排列方式，把 $2$ 号和 $5$ 号的帽子分别放在第一个和第五个小矮人的头上，或者反过来。

样例 2

见附加文件下 [imp1.in](file:imp1.in) 和 [imp1.out](file:imp1.out)。

该样例满足 $n=99999, h_{i}=i$。答案是 $0$。

样例 3

见附加文件下 [imp2.in](file:imp2.in) 和 [imp2.out](file:imp2.out)。

该样例满足 $n=10^5, h_{i}=i$。答案是 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n \leq 10$	$12$
$2$	$n \leq 20$	$30$
$3$	$n \leq 1000$	$30$
$4$	$n \leq 10^5$	$28$