← 返回比赛

已结束 GESP巅峰赛#25

← 上一题下一题 →

A5155 | $太空传送$

来源官方 / 2025

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

小午和小枫在太空站之间探险，一共有 $n$ 个太空站，起初他们在 $1$ 号太空站，他们目标到达 $n$ 号太空站。他们各自拥有一个传送器，这个传送器会根据所在太空站的能源大小改变可传送距离，第 $i$ 个太空站的能源大小为 $a_i$ 。 当位于第 $i$ 个太空站时，可传送到达的目的地为 $[i+1,i+a_i]$ ，但是这个传送器有自己的想法，使用者无法主动控制传送距离，每次启动时，传送器会等概率的将使用者传送到可传送范围内。 小午和小枫想知道他们通过相同次数传送到达 $n$ 号太空站的概率是多少。

输入格式

第一行输入一个正整数 $n$ $(2\leq n\leq 8000)$ ，表示太空站的个数。 第二行输入 $n-1$ 个正整数 $a_i$ $(1\leq a_i\leq n-i)$ ，表示第 $i$ 个太空站的能源大小。

输出格式

输出一个整数，表示小午和小枫通过相同传送次数到达 $n$ 号太空站的概率，取模 $998244353$ 。 形式上说，对于一个分数 $\frac{x}{y}$ ，你需要输出 $x\cdot y^{-1} \bmod 998244353$ ，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \equiv 1 \pmod{998244353}$ 的数。

输入输出样例

输入 #1

5
1 1 1 1

输出 #1

输入 #2

5
4 3 2 1

输出 #2

440198031

C++ 编辑器

输入

输出