题解

思路

把百分数 $P_i$ 在模意义下写成 $q_i=P_i/100$。令 $F_i$ 表示只考虑前 $i$ 层时，从空塔开始成功达到高度 $i$ 的期望操作数，并令 $f_i=F_i-F_{i-1}$。最终答案就是 $F_N=\sum_{i=1}^{N}f_i$。

考虑第一次尝试把当前目标高度推进到 $i$ 时发生的连续掉落。若恰有 $r<i$ 块石头掉落，其概率为 $q_i^r(1-q_i)$，之后需要重新补回最后 $r$ 个高度增量；若全部 $i$ 块都掉落，其概率为 $q_i^i$，之后需要重新补回全部增量。因此有

$$f_i=1+\sum_{r=1}^{i-1}q_i^r(1-q_i)\sum_{j=i-r+1}^{i}f_j+q_i^i\sum_{j=1}^{i}f_j.$$

交换求和顺序并合并等比数列，可以化为

$$f_i=1+\sum_{j=1}^{i}f_jq_i^{i-j+1}.$$

把右侧含 $f_i$ 的一项移到左侧，得到

$$f_i=\frac{1+\sum_{j=1}^{i-1}f_jq_i^{i-j+1}}{1-q_i}.$$

由于 $P_i\le99$，所以 $1-q_i$ 在模 $998\,244\,353$ 意义下一定可逆。

做法

子任务 1 可以把每个可能塔高视为马尔可夫链状态。对每个状态写出一步转移后的期望方程，再用模意义下的高斯消元求出空塔状态的期望。这样直接独立刻画了整个随机过程。

子任务 2 按上式依次计算 $f_i$。对固定的 $i$，枚举所有 $j<i$，同步维护 $q_i$ 的幂即可，最后累加所有 $f_i$。

满分做法利用 $P_i$ 只有 $0$ 到 $99$ 共一百种取值。对每个 $v$ 记 $q_v=v/100$，并在计算第 $i$ 项前维护

$$S_v=\sum_{j=1}^{i-1}f_jq_v^{i-j+1}.$$

于是当前的分子就是 $1+S_{P_i}$。算出 $f_i$ 后，为进入下一位置，对所有 $v$ 更新

$$S_v\leftarrow q_vS_v+f_iq_v^2=q_v(S_v+q_vf_i).$$

每个位置只需更新一百个状态。

正确性证明

连续掉落恰好 $r$ 块后，塔需要重新经历的高度增量正是 $f_{i-r+1},\ldots,f_i$；全部掉落时则需要重新经历 $f_1,\ldots,f_i$。按照这些互斥事件的概率求期望，得到上述关于 $f_i$ 的方程，因此逐项求出的 $f_i$ 与原随机过程一致。

维护量 $S_v$ 在第一个位置前为空和，初值正确。若它在位置 $i$ 前满足定义，加入 $f_i$ 并把所有旧项的指数增加一后，更新式恰好得到位置 $i+1$ 前的新定义。因此由归纳法，每次查询 $S_{P_i}$ 都等于递推式所需的完整和，最终累加得到 $F_N$。

复杂度

子任务 1 的时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。

子任务 2 的时间复杂度为 $O(N^2)$，空间复杂度为 $O(N)$。

满分做法的时间复杂度为 $O(100N)$，空间复杂度为 $O(100+N)$。