官方题解

题目大意

两人从 $1$ 号太空站出发，第 $i$ 个太空站传送范围为 $(i,i+a_i]$ 且等概率传送，求两人使用相同传送次数到达 $n$ 号太空站的概率。

题目思路

通过概率DP思想求解。

设 $dp_{i,j}$ 表示传送了 $j$ 次到达 $i$ 号太空站的概率。

状态转移：$dp_{k,j+1}+=dp_{i,j}$ ，其中 $i<k\leq i+a_i$ 。如果直接这么转移时间复杂度是 $O(n^3)$ 。

但不难发现，转移实际上是一段连续的区间，所以我们可以通过差分前缀和优化。

最终答案为 $\sum_{i=1}^n f(n,i)^2$ 。时间复杂度 $O(n^2)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 8010;
const int INF = 1e18+10;
const int mod = 998244353;

int a[N];
long long Inv[N];
long long dp[N][N];

long long fpow(long long a,long long x){
    long long res=a%mod,ans=1;
    while(x){
        if(x&1) ans=ans*res%mod;
        res=res*res%mod;
        x >>= 1;
    }
    return ans;
}

long long inv(long long a){return fpow(a,mod-2);}

int main(){
    int n;cin>>n;
    for(int i=1;i<n;i++){
        cin>>a[i];
        Inv[a[i]]=inv(a[i]);
    }

    dp[0][1]=1;
    for(int i=1;i<n;i++){
        for(int j=1;j<n;j++){
            int p=dp[i-1][j]*Inv[a[j]]%mod;
            
            dp[i][j+1]=(dp[i][j+1]+p)%mod;
            dp[i][j+a[j]+1]=(dp[i][j+a[j]+1]-p+mod)%mod;
        }
        for(int j=i+1;j<=n;j++){
            dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
        }
    }

    long long ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[i][n]*dp[i][n]%mod)%mod;
    cout<<ans<<endl;
}