abc–263–E

E - Sugoroku 3

关键

其实也就是正常的投色子问题，从后面转移到前面，只是需要用一个后缀和进行优化，懂期望dp后还是挺好写的。

代码

#include <bits/stdc++.h>
using namespace std;
const int M=2e5+5;
#define int long long
const int mod=998244353;

int kpow(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

int inv(int a) {
    return kpow(a,mod-2);
}

int a[M],f[M],sum[M];

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<n;i++)cin>>a[i];
    f[n]=0;
    for(int i=n-1;i>=1;i--) {
        int y=(sum[i+1]-sum[i+a[i]+1]+mod)%mod;
        f[i]=(y*inv(a[i])%mod+(a[i]+1)*inv(a[i])%mod)%mod;
        sum[i]=(sum[i+1]+f[i]%mod);
    }
    cout<<f[1]<<endl;
    return 0;
}
//原来学会概率和期望dp后，这些基础的题目还是挺简单的