問題一覧 > 通常問題

No.3371 Add Insert Operations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : rhoo / テスター : Naru820 jupiter_68 noya2
ProblemId : 12794 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-11-17 12:18:55
コンテストの他の問題:

問題文

数列に対する次の操作を考える。

  • 数列の任意の場所を選び $0$ を挿入する。その後、挿入した場所の左隣に数が存在すれば左隣の数に $1$ を足し、同様に右隣に数が存在すれば右隣の数に $1$ を足す。
$0$ のみからなる長さ $1$ の数列からはじめて、操作を何回か行うことで最終的に長さ $N$ の数列 $A$ になるような操作方法の総数を $998244353$ で割ったあまりを求めよ。
ただし、二つの操作方法が異なるとは、操作回数が異なるか、またはある $i$ に対して $i$ 回目の挿入位置が異なることをいう。

制約

  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i \le 10^9$
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

答えを $1$ 行に出力せよ。

サンプル

サンプル1
入力
3
0 2 0
出力
2

$1$ 回目の操作で一番左に挿入し、 $2$ 回目の操作で一番右に挿入すると数列は $0\;\to\; 0,1\;\to\; 0,2,0$ と変化する。

サンプル2
入力
2
0 0
出力
0

最終的に数列が $0,\; 0$ となる操作方法は存在しない。

サンプル3
入力
20
1 0 5 0 1 1 4 2 0 2 0 7 0 1 1 2 0 5 0 2
出力
454727167

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