[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;
}

https://atcoder.jp/contests/abc263/submissions/33854223