P8682 - Two Frogs

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

In the Lonely Mountain, there are a lot of treasure well protected by dwarfs. Later, one day, the last dragon Smaug came and sensed the treasure being. As known to all, dragons are always much too greedy for treasure. So definitely, the war between dwarfs and Smaug begins.

During the war, two goblins Alice and Bob are turned into frogs by Gandalf, The Grey. In front of them, there are

n

lotus leaves in a line. In order to break the spell, they must jump from the

1

-st lotus leaf to the

n

-th lotus leaf. If the frog is now on the

i

-th lotus leaf instead of the

n

-th lotus leaf, it can jump to a lotus leaf in range

i, i + a_i]

.

Goblins are lack of intelligence and it's also true even after turned into frogs. So Alice and Bob will jump randomly, which means, they will separately pick an available lotus leaf in every jump uniformly at random.

Since Alice and Bob have already being playing games for decades, so they want to know the probability that they jump to the

n

-th lotus leaf with the same count of jumps.

The first line contains an integer

n

\leq n \leq 8\,000)

, denoting the number of lotus leaf.
The second line contains

n - 1

integers

a1,a2,…,an−1a_1, a_2, \ldots, a_{n-1}

, where the

i

-th integer

a_i

\leq a_i \leq n-i)

indicates the range of lotus leaves that can be reached from the

i

-th lotus leaf.

Output a line containing a single integer, indicating the probability that Alive and Bob jump to

n

-th lotus leaf with the same count of jumps, taken modulo

998244353998\,244\,353

.
Formally speaking, let the result, which is a rational number, be

xy\frac{x}{y}

as an irreducible fraction, you need to output

\cdot y^{-1} \bmod{998\,244\,353}

, where

y^{-1}

is a number such that

\cdot y^{-1} \equiv 1 \pmod{998\,244\,353}

. You may safely assume that such

y^{-1}

always exists.

5
1 1 1 1

2022 牛客9

8682: Two Frogs

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签