← 返回题目列表

AtCoder · agc041_f

F. 直方图车

中文机器翻译题面 查看原题

分数: 2000 点

问题陈述

让我们考虑一个正方形网格 N 行和 N 列。 Arbok 切掉了网格的某些部分,这样对于每个 i = 1, 2, \ldots, N,最底部 h_i 方块仍保留在 i左起第 列。 现在,他想将车放入剩余的一些格子中。

车是一种占据一个方格的棋子,可以水平或垂直移动,穿过任意数量的未占据的方格。 车无法穿过被 Arbok 切出的方格。

假设一个方格被覆盖,如果它包含一个车,或者一个车可以一步移动到这个方格。

求出将车放入剩余一些方格中以使每个剩余方格都被覆盖的方法的数量,模数 998244353.

约束

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

输入

输入由标准输入按以下格式给出:

N
h_1 h_2 ... h_N

输出

打印将车放入剩余一些方格中的方法数,以便覆盖每个剩余的方格,模数 998244353.


示例输入 1

2
2 2

示例输出 1

11

任何至少有两个车的位置都可以。有 11 这样的展示位置。


示例输入 2

3
2 1 2

示例输出 2

17

以下 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     

示例输入 3

4
1 2 4 1

示例输出 3

201

示例输入 4

10
4 7 4 8 4 6 8 2 3 6

示例输出 4

263244071