問題一覧 > 通常問題

No.2111 Sum of Diff

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 169
作問者 : bayashiko / テスター : first_vil noimi
2 ProblemId : 8386 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-28 04:48:09

問題文

要素数が NN の整数列 A=(a1,a2,…,aN)A=(a_1,a_2,\ldots,a_N) が与えられます。

AA の (連続とは限らない) 部分列 A′=(a1′,a2′,…,ak′)A'=(a'_1,a'_2,\ldots,a'_k) のうち要素数が 22 以上であるものは、列として等しくても取り出した位置が異なるものを区別すると全部で 2N−N−12^N-N-1 通りあります。

その全てに対する以下の値の総和を 998244353998244353 で割った余りを求めてください。

  • ∑j=1k−1(aj′−aj+1′)\displaystyle \sum_{j=1}^{k-1} (a'_j-a'_{j+1})

入力

NN
a1 a2 … aNa_1\ a_2\ \ldots\ a_N

  • 2≤N≤2×1052\le N\le 2×10^5
  • 0≤ai≤9982443520\le a_i\le 998244352
  • 入力はすべて整数

出力

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

サンプル

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

(3,2,1)(3,2,1) の部分列のうち、要素数が 22 以上のものは (3,2),(3,1),(2,1),(3,2,1)(3,2),(3,1),(2,1),(3,2,1) の 44 つです。それぞれについて式の値を計算すると以下のようになります。

  • (3−2)=1(3-2)=1
  • (3−1)=2(3-1)=2
  • (2−1)=1(2-1)=1
  • (3−2)+(2−1)=1+1=2(3-2)+(2-1)=1+1=2

よって、これらの値の総和である 66 を出力します。

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

(0−1)=−1(0-1)=-1 ですが、 998244353998244353 で割った余りを出力することに注意してください。

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