ABC333F Bomb Game 2 题解

原题链接
洛谷链接

题意

有 $n$ 个人排成一排，从前往后编号为 $1～n$。接下来不断进行以下操作，直到剩下一个人：

• 有 $\frac{1}{2}$ 的概率把排头一炮崩了。
• 有 $\frac{1}{2}$ 的概率使排头站到队尾。

问：对于每个 $1\le i\le n$，编号为 $i$ 的人存活下来的概率是多少？

答案对 $998244353$ 取模。

题解

这是一道肥肠煎蛋（但我没做出来）的 DP。

首先，我们设 $f[i][j]$ 表示剩下 $i$ 个人，从前到后第 $j$ 个人的存活概率。显然，当 $i=1$ 时的存货概率为 $100\%$。因此初始状态为：

$$f[1][1]=1$$

当 $i\ge 2$ 时，$f[i][j]$ 由两部分组成：

第一部分：

第一个人可能被崩了。此时人数减 $1$，而第 $j$ 个人的位置向左移了一位，因此 $j$ 也减 $1$。此时的存活概率为：

$$f[i?1][j?1]$$

第二部分：

第一个人可能回到了队尾。此时人数不变，而第 $j$ 个人位置左移一位，所以 $j$ 减 $1$。此时的存货概率为：

$$f[i][j?1]$$

又因为达成这两种情况的概率都是$\frac{1}{2}$，所以我们得出状态转移方程：

$$f[i][j]=\frac{1}{2}(f[i?1][j?1]+f[i][j?1])$$

但是！你以为这样就可以了吗？

读者：不然呢？

别忘了，当第一个人结束操作，他并不是左移一位，而是回到队尾！因此：

$$f[i][j]=\frac{1}{2}(f[i?1][i]+f[i][i])$$

此时，顺序形成了一个环，不满足 DP 无后效性的原则。

那真的没办法了吗？

不！

发现形成环的部分的 $i$ 都相同，所以我们尝试将 $f[i][1],f[i][2],\dots ,f[i][i]$ 用 $f[i][1]$ 和 $f[i?1][1\dots i]$ 表示出来：

$f[i][1]=f[i][1]$

$f[i][2]=\frac{1}{2}(f[i?1][1]+f[i][1])=\frac{1}{2}f[i?1][1]+\frac{1}{2}f[i][1]$

$f[i][3]=\frac{1}{2}(\frac{1}{2}(f[i?1][1]+f[i][1])+f[i?1][2])=\frac{1}{2}f[i?1][2]+\frac{1}{4}f[i?1][1]+\frac{1}{4}f[i][1]$

$f[i][4]=\dots$

最后得出 $f[i][i]=\frac{1}{2}f[i?1][i?1]+\frac{1}{4}f[i?1][i?2]+?+\frac{1}{2^{i?1}}f[i?1][1]+\frac{1}{2^{i?1}}f[i][1]$。又因 $f[i][1]=\frac{1}{2}(f[i][i]+f[i?1][i])$，所以：

$$f[i][1]=\sum _{k=1}^i\frac{1}{2^{i?k+1}}f[i?1][k]+\frac{1}{2^i}f[i][1]$$

解一下方程，得到：

$$f[i][1]=\frac{2^i}{2^i?1}(\sum _{k=1}^i\frac{1}{2^{i?k+1}}f[i?1][k])$$

这样，我们直接算出了 $f[i][1]$，这样后面的值就可以直接用状态转移方程了。而 $f[n][1\dots n]$ 即为所求。

总结以下式子：

• 初始值：$f[1][1]=1$
• 状态转移方程：
  $$f[i][j]=?\begin{array}{cc}\frac{2^i}{2^i?1}({\sum }_{k=1}^i\frac{1}{2^{i?k+1}}f[i?1][k])& j=1\\ & \\ \frac{1}{2}(f[i?1][j?1]+f[i][j?1])& 2\le j\le i\end{array}$$
• 答案：$f[n][1\dots n]$

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3005,mod=998244353;
int n;
long long f[N][N],p,pw[N],inv[N];
long long power(long long x,int y){
    long long res=1;
    for(;y;y>>=1){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
    }
    return res;
}
int main(){
    pw[0]=inv[0]=1,p=power(2,mod-2);
    cin>>n;
    for(int i=1;i<=n;++i)pw[i]=pw[i-1]*2%mod,inv[i]=inv[i-1]*p%mod;
    f[1][1]=1;
    for(int i=2;i<=n;++i){
        for(int j=1;j<=i;++j)f[i][1]=(f[i][1]+f[i-1][j]*inv[i-j+1]%mod)%mod;
        f[i][1]=f[i][1]*pw[i]%mod*power(pw[i]-1,mod-2)%mod;
        for(int j=2;j<=i;++j)f[i][j]=(f[i][j-1]+f[i-1][j-1])*p%mod;
    }
    for(int i=1;i<=n;++i)cout<<f[n][i]<<' ';
    return 0;
}