問題一覧 > 通常問題

No.3371 Add Insert Operations

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : rhoo / テスター : Naru820 jupiter_68 noya2
お気に入りにしたユーザー ProblemId : 12794 / 自分の提出
問題文最終更新日: 2025-11-17 12:18:55
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 作問ハッカソンコンテスト 003 Day2 (順位表) の他の問題:

Problem Statement

Consider the following operation on a sequence.

  • Choose any position in the sequence and insert $0$ there. Then, if a number exists immediately to the left of the inserted position, add $1$ to that number, and similarly, if a number exists immediately to the right of the inserted position, add $1$ to that number.
Starting from the sequence of length $1$ consisting only of $0$, find the number, modulo $998244353$, of ways of performing the operation some number of times such that the sequence finally becomes the sequence $A$ of length $N$.
Here, two ways of performing the operations are considered different if the numbers of operations differ, or if for some $i$ the insertion positions of the $i$-th operation differ.

Constraints

  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i \le 10^9$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$A_1\; A_2\; \dots\; A_N$

Output

Output the answer in $1$ line.

Sample

Sample 1
Input
3
0 2 0
Output
2

If you insert at the far left in the $1$-st operation and at the far right in the $2$-nd operation, the sequence changes as $0\;\to\; 0,1\;\to\; 0,2,0$.

Sample 2
Input
2
0 0
Output
0

There is no way of performing the operations such that the sequence finally becomes $0,\; 0$.

Sample 3
Input
20
1 0 5 0 1 1 4 2 0 2 0 7 0 1 1 2 0 5 0 2
Output
454727167

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