AtCoder Beginner Contest 263E

ABC263E

期待値DP． \(i \in N\) に対する答えを \(dp_{i}\) とおく．
遷移は
\(dp_{i} = \frac{1}{a[i]+1} \sum_{x \in a[i]+1} dp_{i + x} + 1\).
よって，
\(dp_{i} = \frac{1}{a[i]} \sum_{x \in [1, a[i]+1) } dp_{i + x} + \frac{a[i]+1}{a[i]}\).
初期値は \(dp_{N-1} = 0\)．

実装: 注意
累積和で高速化すれば \(O(N)\)． ただし，逆向きに累積和をとるので，符号も逆．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n;

  cin >> n;

  vll a(n-1); rep(i,n-1) { cin >> a[i]; }

  vector<mint> s(n+1);

  mint now = 0;

  drep(i,n-1){

    now = ( - s[i+a[i]+1] + s[i+1])/mint(a[i]) + mint(a[i]+1)/mint(a[i]);

    s[i] = now + s[i+1];

  }

  cout << now.val() << endl;

 

  return 0;

}