← 返回题目列表

AtCoder · abc263_e

H. 双六3

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 称为 Square 的正方形 1 虽然广场 N。你从 Square 开始 1.

Square 中的每个方格 1 通过广场 N-1 上面有一个骰子。广场上的骰子 i 标有来自的整数 0 通过 A_i,每个发生的概率相等。 (骰子是相互独立的。)

直到到达广场 N,您将在您所在的方格上重复掷骰子。在这里,如果死在广场上 x 滚动整数 y,你去广场 x+y.

求期望值,模 998244353,您掷骰子的次数。

注释

可以证明,求的期望值始终是有理数。此外,如果该值表示 \frac{P}{Q} 使用两个互质整数 P 和 Q,有一个唯一的整数 R 这样 R \times Q \equiv P\pmod{998244353} 和 0 \leq R \lt 998244353。找到这个 R.

约束

  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i \le N-i(1 \le i \le N-1)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_{N-1}

输出

打印答案。


示例输入 1

3
1 1

示例输出 1

4

寻求的期望值为 4,所以 4 。

在到达 Square 之前,这是一种可能的情况 N:

  • 滚动 广场上的 1 广场上 1,然后前往广场 2.
  • 滚动 广场上的 0 广场上 2,并留在那里。
  • 滚动 广场上的 1 广场上 2,然后前往广场 3.

这种情况发生的概率 \frac{1}{8}.


示例输入 2

5
3 1 2 1

示例输出 2

332748122