CF1866M Mighty Rock Tower 题解

· · 题解

概率 DP 好题。

CF1866M 题解

题意简述

叠石头，叠完第 x 个石头后有 P_x 的概率掉下来，掉下来后第 x-1 个石头也有 P_x 的概率掉下来，再掉下来后第 x-2 个石头也有 P_x 的概率掉下来，以此类推。求叠 N 个石头的期望次数。

思路引导

按照常理，我们设的状态应该是 f_i 表示叠到 i 层的期望次数。但稍加考虑，这个状态导出的转移方程非常难想。因此我们考虑对它差分，也就是 f_i 表示从第 i 层叠到 i+1 层的期望次数。

从第 i 层叠到第 i+1 层，有可能直接叠上去，有可能坍塌到第 j 层，也有可能直接坍塌到第 0 层。

其中，第一种情况的期望就是 1；

第二种情况，考虑坍塌到第 j 层的期望。坍塌到第 j 层的概率是 p_i^j(1-p_i)，代价是 \sum_{k=i-j+1}^if_k，故期望是 p_i^j(1-p_i)\sum_{k=i-j+1}^if_k；

第三种情况的概率是 p_i^i，代价是 \sum_{j=1}^if_j，期望是 p_i^i\sum_{j=1}^if_j。

我们直接对这三种情况的期望线性相加，即：

f_i=1+\sum_{j=1}^{i-1}(p_i^j(1-p_i)\sum_{k=i-j+1}^if_k)+p_i^i\sum_{j=1}^if_j =p_if_i+1+\sum_{j=2}^ip_i^jf_{i-j+1}

解得

f_i=\dfrac{1+\sum_{j=2}^ip_i^jf_{i-j+1}}{1-p_i}

这就是状态转移方程了。

然而，如果直接按照这个方程来打的话，时间复杂度为 \mathcal{O}(n^2)，显然会超时。因此我们考虑使用前缀和优化 \sum_{j=2}^ip_i^jf_{i-j+1}。

由于 p 是不定的，但 p 可能的可能的取值又很少，所以我们对于每一种 p 去求前缀和。设 s_i=\sum_{j=2}^ip^jf_{i-j+1}，那么 s_{i+1}=p(s_i+p\cdot f_i)。每一种 p 对应的 s 只用存在一个变量里滚动使用即可。最终答案即为 \sum_{i=1}^Nf_i。

总复杂度为 \mathcal{O}(n)，常数为 100，有点大，但不多。

实现

  1. 读入
  2. 预处理出 p_i。
  3. 动态规划计算答案。

对于 DP 中的每一轮循环（每一个 i）：

  1. 计算 f_i。
  2. 统计进答案。
  3. 处理出前缀和。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int MOD=998244353;
int n,p[200001],inv[1001],f[200001],s[1001];
int qpow(int x,int y) {
    int res=1;
    for(; y; y>>=1) {
        if(y&1)res=(res*x)%MOD;
        x=(x*x)%MOD;
    }
    return res;
}
signed main() {
    cin>>n;
    for(int i=1; i<=n; ++i)scanf("%lld",p+i);
    int tmp=qpow(100,MOD-2);
    for(int i=0; i<=100; ++i)inv[i]=i*tmp%MOD;//inv即p_i
    int ans=0;
    for(int i=1; i<=n; ++i) {
        f[i]=(1+s[p[i]])%MOD*qpow((1+MOD-inv[p[i]])%MOD,MOD-2)%MOD;
        ans=(ans+f[i])%MOD;
        for(int j=0; j<=100; ++j)
            s[j]=(inv[j]*s[j]%MOD+inv[j]*inv[j]%MOD*f[i]%MOD)%MOD;//s[j]是p=j的前缀和
    }
    cout<<ans;
}