题解 : Two Frogs
1. 题意
地址：https://ac.nowcoder.com/acm/contest/33194/B
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 nnn lotus leaves in a line. In order to break the spell, they must jump from the 1-st lotus leaf to the nnn-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 nnn-th lotus leaf with the same count of jumps.
1.2 输入描述:
The first line contains an integer n (2≤n≤8 000), denoting the number of lotus leaf.
The second line contains n−1 integers $a_1,a_2$,…,$a_{n−1}$, where the i-th integer (1≤$a_i$≤n−i) indicates the range of lotus leaves that can be reached from the i-th lotus leaf.
1.3输出描述:
Output a line containing a single integer, indicating the probability that Alive and Bob jump to nnn-th lotus leaf with the same count of jumps, taken modulo 998,244,353.
Formally speaking, let the result, which is a rational number, be $\frac{x}{y}$ as an irreducible fraction, you need to output x⋅y−1 mod 998 244 353, where y−1 is a number such that $y \cdot y^{-1} \equiv 1 \pmod{998,244,353}$. You may safely assume that such $y^{-1}$ always exists.
2.思路
2.1 状态设计与转移方程
显而易见的我们可以得到一个 o($n^3$) 的状态设计和转移方程。令$f[i][j]$表示跳了i次恰好跳到j这个位置的概率。所求答案是
$$
\sum_{i=1}^{n}f[i][n]^2
$$
显而易见的转移方程是：
$$
f[i+1][j+k]=f[i][j]\times\frac{1}{a[j]},k\in [1,a[j]]
$$
在这个过程中注意取模，$\frac{1}{a[j]}$ 要变成 inv(a[j])。这一部分可以线性的预处理出来
2.2 优化
我们不能接受o($n^3$) 的时间复杂度与o($n^2$)的空间复杂度。在方程中枚举k是为了给后面的区间全部加上一个值。我们可以容易的想到使用前缀和进行优化。
当然还可以更轻易地想到使用滚动数组优化以后再使用树状数组或线段树一类的数据结构维护区间信息，当然这样会t，别问怎么知道的
只需要给需要区间加的区间的左端点加上要加的值，在右端点减去这个值。求前缀和的时候就完成了区间加的操作。
另外需要使用滚动数组优化空间复杂度。
3.代码
1 |
|
