C. 建筑物 · AC 题库

第 230 场 AtCoder Regular Contest++

建筑物

Buildings

AtCoder

⌀ 2947

原题

← BD →

建筑物AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

You are given an integer $N$ that is at least $2$ , and $N-1$ integers $C_1,C_2,\dots ,C_{N-1}$ .

给定一个至少为 $2$ 的整数 $N$ ，以及 $N-1$ 个整数 $C_1,C_2,\dots ,C_{N-1}$ 。AI (CI翻译)

There are $N$ buildings lined up on a number line. The $i$ -th building stands at position $i$ and has height $H_i$ . It is known that $(H_1,H_2,\dots ,H_N)$ is a permutation of $(1,2,\dots ,N)$ , but the specific values of $H_1,H_2,\dots ,H_N$ are not known.

数轴上排列着 $N$ 座建筑物。第 $i$ 座建筑物位于位置 $i$ ，高度为 $H_i$ 。已知 $(H_1,H_2,\dots ,H_N)$ 是 $(1,2,\dots ,N)$ 的一个排列，但具体的 $H_1,H_2,\dots ,H_N$ 的值未知。AI (CI翻译)

Find the number, modulo $998244353$ , of possible sequences $(H_1,H_2,\dots, H_N)$ such that the following condition holds for all of $x=1,2,\dots, N-1$ .

求满足以下条件的序列 $(H_1,H_2,\dots ,H_N)$ 的数量，结果对 $998244353$ 取模。对于所有 $x=1,2,\dots, N-1$ ，均需满足：AI (CI翻译)

The number of buildings visible from position $x+0.5$ is $C_x$ . Here, the $i$ -th building is visible if and only if there is no building with height greater than $H_i$ between position $x+0.5$ and position $i$ .

从位置 $x+0.5$ 可以看到的建筑物数量为 $C_x$ 。当且仅当在位置 $x+0.5$ 与位置 $i$ 之间不存在高度大于 $H_i$ 的建筑物时，第 $i$ 座建筑物才是可见的。

AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$2\le N\le 2\times 10^5$
$1\le C_x\le N$
All input values are integers.

$2\le N\le 2\times 10^5$
$1\le C_x\le N$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

N
C_1 C_2 \dots C_{N-1}

N
C_1 C_2 \dots C_{N-1}

AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer.

输出答案。AI (CI翻译)

样例

Input #1

4
2 2 3

Output #1

For example, $(H_1,H_2,H_3,H_4)=(3,4,2,1)$ satisfies the condition. Indeed, - For $x=1$, the buildings visible from position $x+0.5=1.5$ are the first and second buildings; there are $2=C_1$ such buildings. - For $x=2$, the buildings visible from position $x+0.5=2.5$ are the second and third buildings; there are $2=C_2$ such buildings. - For $x=3$, the buildings visible from position $x+0.5=3.5$ are the second, third, and fourth buildings; there are $3=C_3$ such buildings. There are three sequences $(H_1,H_2,H_3,H_4)$ satisfying the condition, including this one.

Input #2

3
2 1

Output #2

There may be no sequence $(H_1,H_2,\dots, H_N)$ satisfying the condition.

Input #3

7
3 3 3 3 4 4

Output #3

题目信息

题号

arc230_c

所属比赛

第 230 场 AtCoder Regular Contest++

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。