区間長ごと・ \(A_i\) ごとに答えへの寄与を考えます。

\(C_{n,i}/n\) を区間長が \(n\) のもののみを考えたときの \(A_i\) の答えへの寄与とします。求める答えは \(\sum_n \sum_i A_i C_{n,i}/n\) です。

これを区間長ごとに差分計算で求めることを考えます。即ち、\(S_n:=\sum_i A_i C_{n,i}\) から \(S_{n+1}\) を求めることを考えます。\(S\) の2回階差は定数時間で求めることができることができるので、\(S\) およびその階差を管理することで、 \(O(N)\) 回の演算で答えを求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;

int main(){
  int N;
  cin >> N;
  vector<int>a(N);
  for(int i=0;i<N;i++)cin >> a[i];
  
  mint s_diff=0;
  for(int i=0;i<N;i++)s_diff+=a[i];

  mint s=0;
  mint ans=0;
  for(int n=1;n<=N;n++){
    s+=s_diff;
    ans+=s/n;
    s_diff-=a[n-1]+a[N-n];
  }
  cout << ans.val() << endl;
}