[ABC263] E - Sugoroku 3
[Q] https://atcoder.jp/contests/abc263/tasks/abc263_e
[A] https://atcoder.jp/contests/abc263/editorial/4552
・考察
1. DP[i]: iからスタートしたとき、ゴール(N-1)に着くまでの操作期待値。
DP[N-1] = 0が初期値
DP[0]が答えになる
2. 操作回数の期待値ってどう求めるの？
DP[0] = 1 / (A + 1) * (DP[0] + DP[1] + ... + DP[A]) + 1
~~~~~~~~~~~ ~~~~
特定の目が出る確率。A+1種類 1回操作するから+1
両辺にDP[0]が存在しているので、式整理をする。
DP[0] = (DP[1] + ... + DP[A] + A + 1) / A
となる。3. DP[0]をdfs(0)で求め始めるとTLE。
途中計算(DP[1] + ... + DP[A])でO(N)かかり、全体O(N^2)になる。
4. DP[N-1] -> DP[N-2] -> ... -> DP[0]の順番で求めればいい。
途中計算(DP[1] + ... + DP[A])の下りは、acc[1] - acc[A+1]累積和し、O(1)になる。
・実装
mint DP[200020];
mint acc[200020];
ll N;
ll A[200020];
// N->0で求める
void solve(ll v) {
ll a = A[v];
DP[v] += acc[v + 1];
if (v + a + 1 < N - 1) DP[v] -= acc[v + a + 1];
DP[v] += (a + 1);
DP[v] /= a;
// 累積
acc[v] += acc[v + 1] + DP[v];
}
int main() {
cincout();
cin >> N;
rep(i, N) cin >> A[i];
for (ll i = N - 2; i >= 0; --i) {
solve(i);
}
cout << DP[0] << endl;
}