整数 \(n\) に対し \(\displaystyle H_n = \sum_{k=1}^n\frac1k\) とします。

解法 \(1\)

\(n=0,1,\ldots,N\) に対し \(\displaystyle B_n=\sum_{k=1}^n A_k\) （累積和）とすると、\(\displaystyle f(l,r)=\frac{B_r-B_{l-1}}{r-l+1}\) が成り立ちます。

したがって、求める値は以下のように式変形できます：

\[ \begin{aligned} &\phantom{=}\sum_{1\le l\le r\le N} f(l,r)\\ &=\sum_{1\le l\le r\le N}\frac{B_r-B_{l-1}}{r-l+1}\\ &=\sum_{r=1}^N\sum_{l=1}^r\frac{B_r}{r-l+1}-\sum_{l=1}^N\sum_{r=l}^N\frac{B_{l-1}}{r-l+1}\\ &=\sum_{r=1}^N H_rB_r - \sum_{l=1}^N H_{N-l+1}B_{l-1}\\ &=\sum_{i=0}^N (H_i-H_{N-i})B_i \end{aligned} \]

したがって、\(H_i\) と \(B_i\) を事前に計算することで答えを計算することができます。

実装例(Python3)

n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (b[i] + a[i]) % MOD
h = [0] * (n + 1)
for i in range(1, n + 1):
    h[i] = (h[i - 1] + pow(i, MOD - 2, MOD)) % MOD
ans = 0
for i in range(n + 1):
    ans += b[i] * (h[i] - h[n - i])
    ans %= MOD
print(ans)

解法 \(2\)

求める値は以下のように式変形できます：

\[ \begin{aligned} &\phantom{=}\sum_{1\le l\le r\le N} f(l,r)\\ &=\sum_{1\le l\le r\le N}\sum_{i=l}^r\frac{A_i}{r-l+1}\\ &=\sum_{1\le l\le i\le r \le N}\frac{A_i}{r-l+1}\\ &=\sum_{i=1}^{N}A_i\sum_{l=1}^i \sum_{r=i}^{N}\frac1{r-l+1}\\ &=\sum_{i=1}^{N}A_i\sum_{l=1}^i (H_{N-l+1}-H_{i-l})\\ &=\sum_{i=1}^{N}A_i\sum_{j=0}^{i-1} (H_{N-j}-H_{j}) \end{aligned} \]

\(\displaystyle \sum_{j=0}^{i-1} (H_{N-j}-H_{j})\) は \(i\) の昇順に計算できるので、答えもこの式から計算することができます。

実装例(Python3)

n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
h = [0] * (n + 1)
for i in range(1, n + 1):
    h[i] = (h[i - 1] + pow(i, MOD - 2, MOD)) % MOD
ans = 0
res = 0
for i in range(n):
    res += h[n - i] - h[i]
    res %= MOD
    ans += a[i] * res
    ans %= MOD
print(ans)