[LnOI2019]加特林轮盘赌

题目

题目背景
加特林轮盘赌是一个养生游戏.

题目描述
与俄罗斯轮盘赌等手枪的赌博不同的是，加特林轮盘赌的赌具是加特林。

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

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

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

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

给出P_0P
0
​
和nn，询问kk号长脖子鹿最终成为唯一幸存者的概率P_kP
k
​
。

输入格式
仅一行三个数，P_0,n,kP
0
​
,n,k.

输出格式
一个浮点数P_{k} P
k
​
，误差应该小于10^{-8}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
说明/提示
对于10%的数据，n <= 100n<=100.

对于30%的数据，n <= 500n<=500.

对于另外20%的数据，k = nk=n.

对于100%的数据，1 <= k <= n <= 10^{4}, 0 <= P_0 <= 1.1<=k<=n<=10
4
,0<=P
0
​
<=1.

所有数据的时间限制为 1000ms 1000ms，空间限制为 256mb 256mb，可开启O2优化。

思路

令pw1[i]表示前(k-1)只长颈鹿自毙i次以内退役的概率，pw2[i]表示编号在k+1~n的长颈鹿自毙i次以内退役的概率。于是pw1[i]=s[i]^{(k-1),pw2[i]=s[i]}(n-k)，其中s[i]为一只长颈鹿自毙i次以内退役的概率，很容易得到s[i]=1-(1-p)^{i，因为一次中枪没有退役的概率为1-p，重复i次均退役则是(1-p)}i，所以i次内退役的概率就是1-(1-p)^{i。因为题目中求的是小数，精度要求是10}-8，所以枚举第k只长颈鹿在第i次中枪时退役且为最后一个退役的概率，把所有概率加起来就行了，可以做到线性复杂度，枚举到10^{6即可（我写的是线性10}5也过了）。注意要特判n=1/k=1/k=n的情况。

代码

#include<bits/stdc++.h>
using namespace std;
double mi[10010];
double dp[2][10010];
int main(){
    int n,m;
    double k;
    cin>>k>>n>>m;
    if(k==0){
        if(n==1)cout<<1<<endl;
        else cout<<0<<endl;
        return 0;
    }
    mi[0]=1;
    for(int i=1;i<=n;i++){
        mi[i]=mi[i-1]*(1.0-k);
    }
    dp[0][1]=1;
    for(int i=2;i<=n;i++){
        double sum=0;
        for(int j=2;j<=i;j++){
            sum+=(dp[0][j-1]*mi[i-j+1]);
        }
        dp[1][1]=k*sum/(1.0-mi[i]);
        for(int j=2;j<=i;j++){
            dp[1][j]=dp[1][j-1]*(1.0-k)+dp[0][j-1]*k;
        }
        for(int j=1;j<=i;j++){
            dp[0][j]=dp[1][j];
        }
    }
    printf("%0.8lf\n",dp[0][m]);
    return 0;
}

本文地址：https://blog.csdn.net/Eric1561759334/article/details/109279513