洛谷 P5249 [LnOI2019]加特林轮盘赌 题解【概率期望】【DP】

作者: wjyyy 分类: DP,概率期望,解题报告 发布时间: 2019-03-11 15:04

点击量:143

很有意思的题目。

题目背景

加特林轮盘赌是一个养生游戏.

题目描述

与俄罗斯轮盘赌等手枪的赌博不同的是,加特林轮盘赌的赌具是加特林。

加特林轮盘赌的规则很简单:在加特林的部分弹夹中填充子弹。游戏的参加者坐在一个圆桌上,轮流把加特林对着自己的头,扣动扳机一秒钟。中枪的自动退出,坚持到最后的就是胜利者。

我们使用的是2019年最新技术的加特林,他的特点是无需预热、子弹无限,每一个人,在每一回合,中枪的概率是完全相同的 $latex P_0$。

每局游戏共有 $latex n$ 只长脖子鹿,从1长脖子鹿开始,按照编号顺序从小到大进行游戏,绕着圆桌不断循环。

游戏可能会循环进行多轮,直到场上仅剩下最后一只长脖子鹿时,游戏结束。

给出 $latex P_0$ 和 $latex n$,询问 $latex k$ 号长脖子鹿最终成为唯一幸存者的概率 $latex P_k$。

输入输出格式

输入格式:

仅一行三个数,$latex P_0,n,k$。

输出格式:

一个浮点数 $latex P_k$,误差应该小于 $latex 10^{-8}$。(请保留更多位数的小数)

输入输出样例

输入样例#1:

0.5 2 1

输出样例#1:

0.33333333

输入样例#2:

0.5 2 2

输出样例#2:

0.66666667

输入样例#3:

0.5 3 1

输出样例#3:

0.23809524

输入样例#4:

0.5 3 2

输出样例#4:

0.28571429

说明

对于 $latex 10\%$ 的数据,$latex n\le 100$。

对于 $latex 30\%$ 的数据,$latex n\le 500$。

对于另外 $latex 20\%$ 的数据,$latex k=n$。

对于 $latex 00\%$ 的数据,$latex 1\le k\le n\le 10^4,0\le P_0\le 1$。

题解

首先需要推出DP/递推方程,然后考虑进一步的优化。因为本题有阶段性,姑且称之为DP。

每次枪会对准一个人,这个人有 $latex P_0$ 的概率挂掉,此时进入 $latex n-1$ 个人的状态

考虑到枪打人是轮流进行的,先后顺序和位次顺序都是有影响的。因此我们设 $latex f[i][j]$ 表示当剩下 $latex i$ 个人时,令枪对准的人是第一个人,第 $latex j$ 个人作为最后一个人存活下来的概率。

“当前的”第一个人有 $latex P_0$ 的概率挂掉。这之后,总人数从 $latex i$ 变成了 $latex i-1$,而枪会指向原来第二个人,那么原来的 $latex f[i][j]$ 在这样的条件下存活的概率是 $latex f[i-1][j-1]$。记为 $latex P_0f[i-1][j-1]$。

注:条件指条件概率。

在 $latex 1-P_0$ 的概率下,当前的第一个人不会挂掉,那么总人数不变,枪会指向原来的第二个人,那么第 $latex j$ 个人就变成了第 $latex j-1$ 个人,原来的 $latex f[i][j]$ 在这样的条件下存活的概率是 $latex f[i][j-1]$,记为 $latex (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
$$
这样由于每次在前一个大阶段有了所有的 $latex f[i-1]$,就有了 $latex f[i][j],1\le j\le i$ 的 $latex i-1$ 个方程。根据逻辑关系我们知道 $latex \sum_{j=1}^if[i][j]=1$,把这个当作第 $latex i$ 个方程,这一组 $latex f[i]$就可以解了。

但是高斯消元是 $latex O(n^3)$ 的,对于每一行都做,那就是 $latex O(n^4)$ 的。实际上每一行可以做到线性。

由于 $latex P_0f[i-1][j-1]$ 已知,我们把这个数设为常数 $latex d_j$,则方程为
$$
f[i][j]=d_j+(1-P_0)f[i][j-1],j\ge 2
$$
此时可以通过这个式子减小第二维的 $latex j$,上面有个式子是
$$
\sum_{j=1}^if[i][j]=1
$$
把这个式子所有的 $latex j$ 都通过上面的方程迭代为 $latex f[i][1]$,方程的形式就变为了 $latex a\cdot f[i][1]+b=1$ 的形式,$latex a,b$ 都是常数,$latex 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}
$$
针对这个式子,从后往前递归处理就可以得到 $latex f[i][1]$ 的系数和常数项了。(实际上从前往后循环也可以,递归更好理解)

注意当 $latex P_0=0$ 时,当且仅当 $latex n=1$ 有 $latex P_1=1$,其余情况下都不可能成为唯一幸存者,需要特判。

时间复杂度 $latex O(n^2)$。

Code:

#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;
}

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

… [Trackback]

[…] Here you will find 43052 more Info to that Topic: wjyyy.top/3343.html […]

/* */