No.2717 Sum of Subarray of Subsequence
タグ : / 解いたユーザー数 92
作問者 :
ecottea
/ テスター :
akakimidori
hamamu
問題文
長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます．$A$ の全ての空でない（連続とは限らない）部分列 $B$ について以下の問題 1 を解き，その答えの和を求めてください：
-
問題 1 : 数列 $B$ の全ての空でない連続部分列 $C$ について以下の問題 2 を解き，その答えの和を求めてください：
- 問題 2 : 数列 $C$ の要素の総和を求めてください．
答えは非常に大きくなることがあるので，答えを $998244353$ で割った余りを出力してください．
ただし部分列，連続部分列ともに，数列として等しい場合でも選んだ要素の添字の集合が異なれば区別します．
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 998244353$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます．
$N$ $A_1 \ \ldots \ A_N$
出力
答えを $998244353$ で割った余りを出力してください． 最後に改行してください．
サンプル
サンプル1
入力
3 1 2 3
出力
50
$A = (1, 2, 3)$ の空でない部分列は $(1, 2, 3), (1, 2), (1, 3), (2, 3), (1), (2), (3)$ です．
$(1, 2, 3)$ についての問題 1 の答えを求めます．$(1, 2, 3)$ の空でない連続部分列は $(1, 2, 3), (1, 2), (2, 3), (1), (2), (3)$ であり，それぞれについての問題 2 の答えを足し合わせると $6 + 3 + 5 + 1 + 2 + 3 = 20$ となります．
残る $(1, 2), (1, 3), (2, 3), (1), (2), (3)$ それぞれについての問題 1 の答えも同様に求めると $6, 8, 10, 1, 2, 3$ となるので，答えは $20 + 6 + 8 + 10 + 1 + 2 + 3 = 50$ です．
サンプル2
入力
2 777777777 777777777
出力
673689250
$998244353$ で割った余りを出力してください．
サンプル3
入力
10 3 1 4 1 5 9 2 6 5 3
出力
176640
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。