F - Histogram Rooks 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 2000 点

問題文

N 行 N 列のマスからなる盤面を考えます。アーボックはこの盤面の一部を切り離し、i = 1, 2, \ldots, N のそれぞれについて、左から i 列目は最も下の h_i マスのみが残されています。 そして、残されたマスのうち何マスかにルークを置こうとしています。

ルークはチェスの駒の一種で、1 マスを占めます。1 回の移動では、何も置かれていないマスの上を縦か横の一方向に何マスでも動けます。 切り離されたマスの上は通れません。

あるマスについて、そのマスにルークが置かれているか、そのマスに 1 回の移動で到達できるルークがあるとき、そのマスは支配下にあるといいます。

残された全マスが支配下に入るように残されたマスのうち何マスかにルークを置く方法の数を 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

2 個以上のルークをどのように置いても条件が満たされ、そのような置き方は 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

Score : 2000 points

Problem Statement

Let us consider a grid of squares with N rows and N columns. Arbok has cut out some part of the grid so that, for each i = 1, 2, \ldots, N, the bottommost h_i squares are remaining in the i-th column from the left. Now, he wants to place rooks into some of the remaining squares.

A rook is a chess piece that occupies one square and can move horizontally or vertically, through any number of unoccupied squares. A rook can not move through squares that have been cut out by Arbok.

Let's say that a square is covered if it either contains a rook, or a rook can be moved to this square in one move.

Find the number of ways to place rooks into some of the remaining squares so that every remaining square is covered, modulo 998244353.

Constraints

  • 1 \leq N \leq 400
  • 1 \leq h_i \leq N
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 ... h_N

Output

Print the number of ways to place rooks into some of the remaining squares so that every remaining square is covered, modulo 998244353.

Sample Input 1

2
2 2

Sample Output 1

11

Any placement with at least two rooks is fine. There are 11 such placements.

Sample Input 2

3
2 1 2

Sample Output 2

17

The following 17 rook placements satisfy the conditions (R denotes a rook, * denotes an empty square):

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

Sample Input 3

4
1 2 4 1

Sample Output 3

201

Sample Input 4

10
4 7 4 8 4 6 8 2 3 6

Sample Output 4

263244071