根据期望的线性性,总工资的期望等于在每一个 \(i\) 处获得的工资的期望之和,而在 \(i\) 处获得的工资的期望 \(E(i)=A_i\times p(i)\),其中 \(p(i)\) 表示掷骰子掷到 \(i\) 且有效的概率。
初始 \(p(0)=1\),则只有从 \(0\sim i-1\) 掷骰子掷到 \(i\) 时才有效,显然每一种情况掷到 \(i\) 的概率均为 \(\frac{1}{n}\),因此有转移方程:
\[p(i)=\frac{1}{n}\sum_{j=0}^{i-1}p(j)
\]
使用前缀和优化即可做到 \(O(n)\)。
// Problem: E - Revenge of "The Salary of AtCoder Inc."
// Contest: AtCoder - Panasonic Programming Contest 2023(AtCoder Beginner Contest 326)
// URL: https://atcoder.jp/contests/abc326/tasks/abc326_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 3e5 + 5, mod = 998244353;
ll n, a[N], inv[N], p[N], Sp[N], ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i, 1, n) cin >> a[i];
inv[0] = inv[1] = 1;
rep(i, 2, n) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
p[0] = Sp[0] = 1;
rep(i, 1, n) {
p[i] = Sp[i - 1] * inv[n] % mod;
Sp[i] = (Sp[i - 1] + p[i]) % mod;
ans = (ans + p[i] * a[i] % mod) % mod;
}
cout << ans << endl;
return 0;
}