E - Revenge of "The Salary of AtCoder Inc."

dp

考え方

操作が終わる方から決まるので，$N$から小さい順に考える．

• $\mathrm{dp}[i]=i$が出たあとでもらえる給料の期待値．
• $\mathrm{dp}[N]=A[N]$
• $\displaystyle \mathrm{dp}[i] = A[i] + \sum_{j=i+1}^{N}\mathrm{dp} [j] \times \frac{1}{N}$

答えは$ \displaystyle \sum_{j=1}^{N}\mathrm{dp} [j] \times \frac{1}{N}$

回答例

modの逆数 - 競プロはじめましたを参照．

N = int(input())
A = list(map(int, input().split()))
mod = 998244353

invN = pow(N, mod - 2, mod)

dp = [0] * N
dp[-1] = A[-1]
SUM = A[-1]
for i in range(N - 1):
    dp[-1 - i - 1] = A[-1 - i - 1] + SUM * invN
    dp[-1 - i - 1] %= mod

    SUM += dp[-1 - i - 1]
    SUM %= mod

print((SUM * invN) % mod)