/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
正整数 N と長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
f(l,r) を A_l,A_{l+1},\ldots,A_r の（算術）平均として定義します。
\displaystyle \sum_{1\le l\le r\le N} f(l,r) を \text{mod }{998244353} で求めてください。
有理数 \text{mod }{998244353} の定義
この問題の制約のもとでは、求める有理数を既約分数 \frac{P}{Q} で表した時、Q {{}\not\equiv{}} 0 \pmod{998244353} となることが証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。
制約
- 1\le N\le 5\times 10^5
- 0\le A_i < 998244353
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
2 2 3
出力例 1
499122184
\displaystyle f(1,1)=2,f(1,2)=\frac{2+3}2=\frac52,f(2,2)=3 です。したがって、\displaystyle \sum_{1\le l\le r\le N} f(l,r)=2+\frac52+3=\frac{15}2 です。
\displaystyle \frac{15}2 は \text{mod }{998244353} で 499122184 なので、499122184 を出力してください。
入力例 2
6 1 2 3 4 5 6
出力例 2
499122250
入力例 3
9 3 1 4 1 5 9 2 6 5
出力例 3
855638200
Score : 450 points
Problem Statement
You are given a positive integer N and a length-N integer sequence A=(A_1,A_2,\ldots,A_N).
Define f(l,r) as the (arithmetic) mean of A_l,A_{l+1},\ldots,A_r.
Find \displaystyle \sum_{1\le l\le r\le N} f(l,r), modulo 998244353.
Definition of a rational number modulo 998244353
Under the constraints of this problem, it can be proved that the rational number to be found is always an irreducible fraction \frac{P}{Q} such that Q {{}\not\equiv{}} 0 \pmod{998244353}. Thus, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Output this R.
Constraints
- 1\le N\le 5\times 10^5
- 0\le A_i < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Output the answer.
Sample Input 1
2 2 3
Sample Output 1
499122184
We have \displaystyle f(1,1)=2,f(1,2)=\frac{2+3}2=\frac52,f(2,2)=3. Thus, \displaystyle \sum_{1\le l\le r\le N} f(l,r)=2+\frac52+3=\frac{15}2.
\displaystyle \frac{15}2 in modulo-998244353 expression is 499122184, so output 499122184.
Sample Input 2
6 1 2 3 4 5 6
Sample Output 2
499122250
Sample Input 3
9 3 1 4 1 5 9 2 6 5
Sample Output 3
855638200