ABC468 E - Sum of Average

考え方

全ての区間について、「その区間の合計/個数」を合計すればよい。
個数が同じものでまとめて処理することを考える。

長さ $1$ の区間は全部で $N$ 個あり、各数が $1$ 回ずつ足される。
長さ $2$ の区間は全部で $N-1$ 個あり、両端は $1$ 回ずつ、残りは $2$ 回ずつ足される。

以下同じように考えていくと、長さ $k$ の区間の総和は、以下のように求められる。

• 長さ $k-1$ での総和を用意する
• 先頭から始まる区間の分、つまり先頭から $k-1$ 個の総和を引く
• 全ての区間を前に $1$ 伸ばす、つまり先頭から $N-k+1$ 個の総和を足す

この計算は、累積和を持っておけば、各 $k$ について $O(1)$ で済む。
こうして求めた長さ $k$ の区間の総和を $k$ で割った余りを足しこんでいけば答えが得られる。
計算量は $O(N)$。

入力例2での動作

入力を受け取る。

n: 6
a: {1, 2, 3, 4, 5, 6}

累積和 sum を作る。

sum: {0, 1, 3, 6, 10, 15, 21}

result と s は、どちらも $0$ で初期化されている。

result: 0
s: 0

$i=1$ のとき、長さ $1$ の区間の総和の総和を求める。

$$
s=0+\mathrm{sum}[6]-\mathrm{sum}[0]=21
$$

これは、長さ $1$ の各区間の総和をすべて足した

$$
1+2+3+4+5+6=21
$$

に一致する。
長さ $1$ で割った $21$ を result に加える。

result: 21

mod $998244353$ での値は $21$（本来の分数値は $21/1$）となる。

$i=2$ のとき、s を次のように更新する。

$$
s=21+\mathrm{sum}[5]-\mathrm{sum}[1]
=21+15-1
=35
$$

これは、長さ $2$ の各区間の総和をすべて足した

$$
(1+2)+(2+3)+(3+4)+(4+5)+(5+6)=35
$$

に一致する。
長さ $2$ で割った $35/2$ を result に加える。
$35/2$ の mod $998244353$ での値は $499122194$ である。

result: 499122215

mod $998244353$ での値は $499122215$（本来の分数値は $77/2$）となる。

$i=3$ のとき、s を次のように更新する。

$$
s=35+\mathrm{sum}[4]-\mathrm{sum}[2]
=35+10-3
=42
$$

これは、長さ $3$ の各区間の総和をすべて足した

$$
(1+2+3)+(2+3+4)+(3+4+5)+(4+5+6)=42
$$

に一致する。
長さ $3$ で割った $42/3=14$ を result に加える。

result: 499122229

mod $998244353$ での値は $499122229$（本来の分数値は $105/2$）となる。

$i=4$ のとき、s を次のように更新する。

$$
s=42+\mathrm{sum}[3]-\mathrm{sum}[3]
=42+6-6
=42
$$

これは、長さ $4$ の各区間の総和をすべて足した

$$
(1+2+3+4)+(2+3+4+5)+(3+4+5+6)=42
$$

に一致する。
長さ $4$ で割った $42/4=21/2$ を result に加える。
$21/2$ の mod $998244353$ での値は $499122187$ である。

result: 63

mod $998244353$ での値は $63$（本来の分数値は $63/1$）となる。

$i=5$ のとき、s を次のように更新する。

$$
s=42+\mathrm{sum}[2]-\mathrm{sum}[4]
=42+3-10
=35
$$

これは、長さ $5$ の各区間の総和をすべて足した

$$
(1+2+3+4+5)+(2+3+4+5+6)=35
$$

に一致する。
長さ $5$ で割った $35/5=7$ を result に加える。

result: 70

mod $998244353$ での値は $70$（本来の分数値は $70/1$）となる。

$i=6$ のとき、s を次のように更新する。

$$
s=35+\mathrm{sum}[1]-\mathrm{sum}[5]
=35+1-15
=21
$$

これは、長さ $6$ の区間の総和

$$
1+2+3+4+5+6=21
$$

に一致する。
長さ $6$ で割った $21/6=7/2$ を result に加える。
$7/2$ の mod $998244353$ での値は $499122180$ である。

result: 499122250

mod $998244353$ での値は $499122250$（本来の分数値は $147/2$）となる。

注意点

累積和や掛け算の途中結果は、int 型からはみ出る。
long long 型を用いること。

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 し、割り算は $998244353-2$ 乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法のアルゴリズムも用意しておくこと。

別解

特になし。