実は、求める期待値は以下の式で求めることができます。

• \(\displaystyle \sum^{N}_{i=1} A_i \times \) ( 手順中で \(A_i\) が支払われる確率 )

では、手順中で \(A_i\) が支払われる確率 \(p_i\) を求めていきましょう。

便宜上、 \(p_0=1\) とします。
このとき、 \(\displaystyle p_i = \frac{1}{N} \sum_{j=0}^{i-1} p_j\) と求められます。
説明 : \(\frac{1}{N} p_j\) で、 \(x=j\) の状態から直接出目 \(i\) を出して \(A_i\) 円を受け取る確率を表現しています。

これは、累積和を利用することで時間計算量 \(O(N)\) で求められます。
なお、 \({}\bmod{998244353}\) 上で \(N\) で割るという操作は \(N\) のモジュラ逆数を掛けることで実現されます。 参考

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

#define mod 998244353
#define FACSIZE 1048576

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

int main(){
  long long n;
  cin >> n;
  long long invn=modular_inverse(n);
  long long p=invn,res=0;
  for(long long i=0;i<n;i++){
    long long a;
    cin >> a;
    res+=p*a;res%=mod;
    p+=p*invn;p%=mod;
  }
  cout << res << "\n";
  return 0;
}