Sum of Averages (subarray)

部分列の長さを固定してすべての部分列に渡った総和を計算し、それを長さで割ったものの和が答えとなります。すると$k = 1,2,\cdots,N$について、$A$のすべての長さ$k$の連続部分列の総和が列挙できればいいです。それは$A$の累積和を$S(0-indexed)$として $(S[k] - S[0]) + (S[k + 1] - S[1]) + \cdots + (S[N] - S[N - k]) = \sum_{i=N - k + 1}^{N} S[i]\enspace- \sum_{i=0}^{k-1} S[i]$とかけます。$L_k = \sum_{i=0}^{k-1} S[i],R_k = \sum_{i=N - k + 1}^{N} S[i]$とすると$L_1 = S[0],R_1 = S[N],L_k = L_{k-1} + S[k - 1],R_k = R_{k-1} + S[N - k + 1]$が成り立ちます。 これを用いると $k = 1,2,\cdots,N$の順に$L_k,R_k$を計算しながら$\frac{R_k - L_k}{k}$を足し合わせていくと答えが求まります。よって$mod = 998244353$として時間計算量$O(N\log mod)$でこの問題を解くことができました。