AT_agc041_f.[AGC041F] Histogram Rooks

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

我们考虑一个有 $N$ 行 $N$ 列的方格网。Arbok 剪掉了网格的一部分，使得对于每个 $i = 1, 2, \ldots, N$ ，从左往右第 $i$ 列的最底部剩下 $h_i$ 个方格。现在，他想在剩下的某些方格中放置车。

车是一种国际象棋棋子，占据一个格子，可以沿水平方向或垂直方向移动任意步数，只要经过的格子没有被占用。车不能穿过被 Arbok 剪掉的格子。

我们称一个格子被覆盖，当且仅当它本身有车，或者有车能一步移动到该格子。

请你计算有多少种方式可以在剩下的格子中放置车，使得每一个剩下的格子都被覆盖。答案对 $998244353$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$

$h_1$ $h_2$ $...$ $h_N$

输出格式

输出一个整数，表示有多少种放置车的方案，使得每一个剩下的格子都被覆盖。答案对 $998244353$ 取模。

输入输出样例

输入#1
```
2
2 2
```
输出#1
```
11
```
输入#2
```
3
2 1 2
```
输出#2
```
17
```
输入#3
```
4
1 2 4 1
```
输出#3
```
201
```
输入#4
```
10
4 7 4 8 4 6 8 2 3 6
```
输出#4
```
263244071
```

说明/提示

数据范围

$1 \leq N \leq 400$
$1 \leq h_i \leq N$
所有输入值均为整数。

样例解释 1

只要至少放两个车的任意方案都可以。这样的方案共有 $11$ 种。

样例解释 2

以下 $17$ 种放置车的方案满足条件（R 表示有车，* 表示空格）：

R *     * R     * *     R R     R R     R R     
**R     R**     R*R     R**     *R*     **R     


R *     R *     * R     * R     * *     R R     
R*R     *RR     RR*     R*R     RRR     RR*     


R R     R R     R *     * R     R R     
R*R     *RR     RRR     RRR     RRR

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页