問題一覧 > 通常問題

No.2792 Security Cameras on Young Diagram

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : 👑 箱星箱星 / テスター : dadasdadas
17 ProblemId : 10222 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-23 08:39:54

問題文

箱星さんはヤング図形が大好きです。

広義単調減少列 $A=(A_1,A_2,\ldots,A_N)$ のヤング図形を考えます。すなわち、上から $i$ 行目に $A_i$ 個の正方形を左詰めで並べます。

ヤング図形のマスに下向きまたは右向きのカメラを設置します。あるマスに下向きのカメラを設置すると、そのマス自身とそのマスより下のマスが監視されます。あるマスに右向きのカメラを設置すると、そのマス自身とそのマスより右のマスが監視されます。

次の条件をすべて満たすようにカメラを設置する方法の数を $998244353$ で割った余りを求めてください。

  • 各マスについて、そのマスにあるカメラの個数は $0$ 個または $1$ 個である。
  • どのマスもあるカメラによって監視される。
  • カメラの存在するマスは他のカメラによって監視されない。

制約

  • $1\le N\le 10^5$
  • $1\le A_i\le 10^5$
  • $A_1\ge A_2\ge\cdots\ge A_N$
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。
$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

答えを出力してください。

サンプル

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

サンプル2
入力
3
111 22 3
出力
375

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

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