問題一覧 > 通常問題

No.2717 Sum of Subarray of Subsequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 99
作問者 : ecottea / テスター : akakimidori hamamu
3 ProblemId : 10593 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-25 19:33:09

問題文

長さ NN の数列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N) が与えられます．AA の全ての空でない（連続とは限らない）部分列 BB について以下の問題 1 を解き，その答えの和を求めてください：

  • 問題 1 : 数列 BB の全ての空でない連続部分列 CC について以下の問題 2 を解き，その答えの和を求めてください：

    • 問題 2 : 数列 CC の要素の総和を求めてください．

答えは非常に大きくなることがあるので，答えを 998244353998244353 で割った余りを出力してください．

ただし部分列，連続部分列ともに，数列として等しい場合でも選んだ要素の添字の集合が異なれば区別します．

制約

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤Ai<9982443530 \leq A_i < 998244353
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます．

NN
A1 … ANA_1 \ \ldots \ A_N

出力

答えを 998244353998244353 で割った余りを出力してください． 最後に改行してください．

サンプル

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

A=(1,2,3)A = (1, 2, 3) の空でない部分列は (1,2,3),(1,2),(1,3),(2,3),(1),(2),(3)(1, 2, 3), (1, 2), (1, 3), (2, 3), (1), (2), (3) です．

(1,2,3)(1, 2, 3) についての問題 1 の答えを求めます．(1,2,3)(1, 2, 3) の空でない連続部分列は (1,2,3),(1,2),(2,3),(1),(2),(3)(1, 2, 3), (1, 2), (2, 3), (1), (2), (3) であり，それぞれについての問題 2 の答えを足し合わせると 6+3+5+1+2+3=206 + 3 + 5 + 1 + 2 + 3 = 20 となります．

残る (1,2),(1,3),(2,3),(1),(2),(3)(1, 2), (1, 3), (2, 3), (1), (2), (3) それぞれについての問題 1 の答えも同様に求めると 6,8,10,1,2,36, 8, 10, 1, 2, 3 となるので，答えは 20+6+8+10+1+2+3=5020 + 6 + 8 + 10 + 1 + 2 + 3 = 50 です．

サンプル2
入力
2
777777777 777777777
出力
673689250

998244353998244353 で割った余りを出力してください．

サンプル3
入力
10
3 1 4 1 5 9 2 6 5 3
出力
176640

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