問題一覧 > 通常問題

No.2792 Security Cameras on Young Diagram

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 93
作問者 : 👑 箱星 / テスター : dadas
お気に入りにしたユーザー ProblemId : 10222 / 自分の提出
問題文最終更新日: 2024-06-23 08:39:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 434 (順位表) の他の問題:

Problem Statement

Hakoboshi loves Young diagrams.

Consider the Young diagram of a non-increasing sequence $A=(A_1,A_2,\ldots,A_N)$. That is, in the $i$-th row from the top, $A_i$ squares are placed, aligned to the left.

You place downward-facing or rightward-facing cameras on cells of the Young diagram. If a downward-facing camera is placed on a cell, that cell itself and the cells below it are monitored. If a rightward-facing camera is placed on a cell, that cell itself and the cells to the right of it are monitored.

Find the number of ways to place cameras so that all of the following conditions are satisfied, modulo $998244353$.

  • For each cell, the number of cameras on that cell is $0$ or $1$.
  • Every cell is monitored by some camera.
  • A cell containing a camera is not monitored by any other camera.

Constraints

  • $1\le N\le 10^5$
  • $1\le A_i\le 10^5$
  • $A_1\ge A_2\ge\cdots\ge A_N$
  • All input values are integers.

Input

The input is given from standard input in the following format.
$N$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Output the answer.

Sample

Sample 1
Input
2
3 2
Output
7

Sample 2
Input
3
111 22 3
Output
375

Sample 3
Input
6
3 2 2 1 1 1
Output
14

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。