巅峰赛#25 T4
原题链接：74559.太空传送
2025-09-14 22:54:02
发布于：浙江
8阅读
0回复
0点赞
注释小剧场
观察这道题数字都给的挺小，唯一我们要注意的是要开long long，因为是逆元等的运算，所以即便步步取余也难逃爆int
别的其实就没有好说的了，一道纯纯数学题；
通过演算我们完全可以清楚看出
到达一点的概率=上一点到达概率x(1/上一点可到达点数)
step为步数，i为当前点，t为上一节点，ks表示计算从t到达i的概率逆元
dp[i][step+1]+=dp[t][step]*ks(1,a[t])
//t<i<=t+a[t]
这里用二维表示方便理解
最后发现复杂度硬算还是略高
我们直接预处理ks数组，以及用差分进行优化·
其余需要注意点都由注释标在代码中
AC code:
#include<bits/stdc++.h>
using namespace std;
const long long M=998244353;
int n;
long long dp[9010];//第i个空间站走j步的方案数的概率
//dp[i][j]=(dp[t][j-1]/a[t])+dp[i][j];
//通过广搜会超时，O(n^3 log n)直接爆了;
//通过打表（666，耗费一节数学课还被老师肘飞了）
//可得每次搜索到一个点t时，他可以到达的节点表达式都是：
//dp[i][step+1]+=dp[t][step]*ks(1,a[t]) t<i<=t+a[t]
//我们可以将空间优化成一维，每次保存前一步的结果即可
//范围累加一个值自己想是什么算法
long long cf[8010];
long long ksm(long long a,long long b){
if(b==0)return 1;
if(b==1)return a;
long long ans=ksm(a,b/2)%M;
ans=ans*ans%M;
if(b%2==1)return ans*a%M;
else return ans;
}
long long ks[100010];
int main(){
cin>>n;
long long a[8010];
for(int i=1;i<n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
ks[i]=ksm(i,M-2);//预处理，因为每次算逆元时都是（1，x）
}
dp[1]=1;
long long f=0;
for(int j=1;j<n;j++){//遍历步数
//long long k=0;
memset(cf,0,sizeof cf);//每一行差分都是独立的
for(int i=1;i<n;i++){
if(dp[i]==0)continue;//都不可能到达了还算啥啊
int l=i+1,r=i+a[i];
if(r>n)r=n;
cf[l]=(cf[l]+dp[i]*ks[a[i]]%M+M)%M;//加M防出现负数(其实左端点不用)
cf[r+1]=(cf[r+1]-dp[i]*ks[a[i]]%M+M)%M;
}
//计算玩概率差分后就可以累加保存了
for(int i=1;i<=n;i++){
cf[i]=(cf[i]+cf[i-1])%M;
dp[i]=cf[i];
}
f=(f+dp[n]*dp[n]%M)%M;
}
cout<<f;
}
其实不值绿题，如果没有逆元运算转而求方案数，黄题都多余了
这里空空如也
有帮助，赞一个