题解 P5249 【[LnOI2019]加特林轮盘赌】
wjyyy
2019-03-11 15:04:38
## 题解
**[博客传送门]( http://www.wjyyy.top/3343.html)**
首先需要推出DP/递推方程，然后考虑进一步的优化。因为本题有阶段性，姑且称之为DP。
每次枪会对准一个人，这个人有 $P_0$ 的概率挂掉，**此时进入 $n-1$ 个人的状态**。
考虑到枪打人是轮流进行的，先后顺序和位次顺序都是有影响的。因此我们设 $f[i][j]$ 表示当剩下 $i$ 个人时，令枪对准的人是第一个人，第 $j$ 个人作为最后一个人存活下来的概率。
**“当前的”第一个人**有 $P_0$ 的概率挂掉。这之后，总人数从 $i$ 变成了 $i-1$，而枪会指向原来第二个人，那么原来的 $f[i][j]$ 在这样的**条件**下存活的概率是 $f[i-1][j-1]$。记为 $P_0f[i-1][j-1]$。
> **注：**条件指条件概率。
在 $1-P_0$ 的概率下，当前的第一个人不会挂掉，那么总人数不变，枪会指向原来的第二个人，那么第 $j$ 个人就变成了第 $j-1$ 个人，原来的 $f[i][j]$ 在这样的条件下存活的概率是 $f[i][j-1]$，记为 $(1-P_0)f[i][j-1]$。
因此有
$$f[i][j]=P_0f[i-1][j-1]+(1-P_0)f[i][j-1],j\ge 2$$
这样由于每次在前一个大阶段有了所有的 $f[i-1]$，就有了 $f[i][j],1\le j\le i$ 的 $i-1$ 个方程。根据逻辑关系我们知道 $\sum_{j=1}^if[i][j]=1$，把这个当作第 $i$ 个方程，这一组 $f[i]$就可以解了。
但是高斯消元是 $O(n^3)$ 的，对于每一行都做，那就是 $O(n^4)$ 的。实际上每一行可以做到线性。
由于 $P_0f[i-1][j-1]$ 已知，我们把这个数设为常数 $d_j$，则方程为
$$f[i][j]=d_j+(1-P_0)f[i][j-1],j\ge 2$$
此时可以通过这个式子减小第二维的 $j$，上面有个式子是
$$\sum_{j=1}^if[i][j]=1$$
把这个式子所有的 $j$ 都通过上面的方程迭代为 $f[i][1]$，方程的形式就变为了 $a\cdot f[i][1]+b=1$ 的形式，$a,b$ 都是常数，$f[i][1]$ 就被解出来了，再通过方程递推即可。
$$\begin{aligned}&f[i][1]&+&f[i][2]&+&\cdots+f[i][i]\\ =&f[i][1]&+&d_2+(1-P_0)f[i][1]&+&\cdots+d_i+(1-P_0)f[i][i-1]\end{aligned}$$
针对这个式子，从后往前递归处理就可以得到 $f[i][1]$ 的系数和常数项了。（实际上从前往后循环也可以，递归更好理解）
注意当 $P_0=0$ 时，当且仅当 $n=1$ 有 $P_1=1$，其余情况下都不可能成为唯一幸存者，需要特判。
时间复杂度 $O(n^2)$。
## Code：
```cpp
#include<cstdio>
#include<cstring>
#define db double
db f[10010],d[10010],tmp,sum,p;
db a,b;
//a代表 f(x-1) 中 f1 的系数 b 代表 f(x-1) 的常数项
void calc(int x)
{
if(x==1)
{
a=1;
tmp=1;
b=0;
return;
}
calc(x-1);
//tmp 代表已经积累的 f1 的系数 sum 代表常数项
tmp+=(1-p)*a;
sum+=p*d[x]+(1-p)*b;
a=(1-p)*a;
b=p*d[x]+(1-p)*b;
}
int main()
{
int n,m;
scanf("%lf%d%d",&p,&n,&m);
if(p==0)
{
puts(n>1?"0":"1");
return 0;
}
f[1]=1;
d[2]=1;
for(int i=2;i<=n;++i)
{
tmp=0.0,sum=0.0;
calc(i);
f[1]=(1-sum)/tmp;
for(int j=2;j<=i;++j)
f[j]=p*d[j]+(1-p)*f[j-1];
for(int j=2;j<=i+1;++j)
d[j]=f[j-1];
}
printf("%.10lf\n",f[m]);
return 0;
}
```