注释小剧场 观察这道题数字都给的挺小，唯一我们要注意的是要开long long，因为是逆元等的运算，所以即便步步取余也难逃爆int 别的其实就没有好说的了，一道纯纯数学题； 通过演算我们完全可以清楚看出 到达一点的概率=上一点到达概率x(1/上一点可到达点数) step为步数，i为当前点，t为上一节点，ks表示计算从t到达i的概率逆元 这里用二维表示方便理解 最后发现复杂度硬算还是略高 我们直接预处理ks数组，以及用差分进行优化· 其余需要注意点都由注释标在代码中 AC code: 其实不值绿题，如果没有逆元运算转而求方案数，黄题都多余了

题目大意 两人从 111 号太空站出发，第 iii 个太空站传送范围为 (i,i+ai](i,i+a_i](i,i+ai ] 且等概率传送，求两人使用相同传送次数到达 nnn 号太空站的概率。 题目思路 通过概率DP思想求解。 设 dpi,jdp_{i,j}dpi,j 表示传送了 jjj 次到达 iii 号太空站的概率。 状态转移：dpk,j+1+=dpi,jdp_{k,j+1}+=dp_{i,j}dpk,j+1 +=dpi,j ，其中 i<k≤i+aii<k\leq i+a_ii<k≤i+ai 。如果直接这么转移时间复杂度是 O(n3)O(n^3)O(n3) 。 但不难发现，转移实际上是一段连续的区间，所以我们可以通过差分前缀和优化。 最终答案为 ∑i=1nf(n,i)2\sum_{i=1}^n f(n,i)^2∑i=1n f(n,i)2 。时间复杂度 O(n2)O(n^2)O(n2) 。 参考代码