問題一覧 > 通常問題

No.2149 Vanitas Vanitatum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : 👑 箱箱 / テスター : hotman78hotman78
6 ProblemId : 8281 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-02 20:15:04

問題文

広義単調増加な正整数列 $A_1,A_2,\ldots,A_N$ が与えられます。以下の $2$ 種類の操作を考えます。

  • $A_i\ge 2$ となる添字 $i$ を $1$ つ選び、$A_i$ から $2$ を引く。操作後も数列は広義単調増加でなければならない。
  • $A_i=A_{i+1}\ge 1$ となる添字 $i$ を $1$ つ選び、$A_i,A_{i+1}$ から $1$ を引く。操作後も数列は広義単調増加でなければならない。

どちらの操作も行えなくなるまで操作を繰り返します。$A_1,A_2,\ldots,A_N$ をすべて $0$ にする操作方法の数を $998244353$ で割った余りを求めてください。

制約

  • $1\le N\le 1000$
  • $1\le A_1\le A_2\le\cdots\le A_N\le 1000$
  • 入力はすべて整数

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

操作方法の数を $998244353$ で割った余りを出力してください。

サンプル

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

次の $3$ 通りがあります。

  • $(3,3) \to (2,2) \to (1,1) \to (0,0)$
  • $(3,3) \to (2,2) \to (0,2) \to (0,0)$
  • $(3,3) \to (1,3) \to (1,1) \to (0,0)$
サンプル2
入力
5
1 3 5 7 9
出力
0

すべて $0$ にすることはできません。

サンプル3
入力
4
1000 1000 1000 1000
出力
55019937

$998244353$ で割った余りを求めてください。

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