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}

累積和は次のようになる。

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

長さ $1$ の区間和の総和は $0+(21-0)=21$ となる。

長さ $2$ では、直前の $21$ に累積和を使って差分を反映し、
$21+(15-1)=35$ となる。

以降も同様に更新すると、各長さについて次の値になる。

したがって、答えは $499122250$ となる。

注意点

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

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

別解

特になし。