BZOJ#2318. Spoj4060 game with probability Problem

Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。

现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。

第一行一个正整数t，表示数据组数。

对于每组数据，一行三个数n，p，q。

对于每组数据输出一行一个实数，表示Alice胜利的概率，保留6位小数

1.推式子

设 f[i] f [ i ] 表示剩i个石头的时候先手投硬币的获胜概率， g[i] g [ i ] 表示后手时的获胜概率, p0,q0 p 0 , q 0 分别为Alice正面朝上的概率与Bob正面朝上的概率

则 f[0]=0 g[0]=1 f [ 0 ] = 0   g [ 0 ] = 1

由于 f[i] f [ i ] 有 p0 p 0 的概率拿走一个石头 状态就有 p0 p 0 的概率转移到 g[i−1] g [ i − 1 ] 有 1−p0 1 − p 0 的概率转移到 g[i] g [ i ]

故 f[i]=p0∗g[i−1]+(1−p0)∗g[i] f [ i ] = p 0 ∗ g [ i − 1 ] + ( 1 − p 0 ) ∗ g [ i ]

同理可以推出 g[i]=q0∗f[i−1]+(1−q0)∗f[i] g [ i ] = q 0 ∗ f [ i − 1 ] + ( 1 − q 0 ) ∗ f [ i ]

解两式构成的方程组可得

f[i]=p0∗g[i−1]+q0∗(1−p0)∗f[i−1]p0+q0−p0∗q0 f [ i ] = p 0 ∗ g [ i − 1 ] + q 0 ∗ ( 1 − p 0 ) ∗ f [ i − 1 ] p 0 + q 0 − p 0 ∗ q 0

g[i]=q0∗f[i−1]+p0∗(1−q0)∗g[i−1]p0+q0−p0∗q0 g [ i ] = q 0 ∗ f [ i − 1 ] + p 0 ∗ ( 1 − q 0 ) ∗ g [ i − 1 ] p 0 + q 0 − p 0 ∗ q 0

2.讨论

题面中的 p,q p , q 并不都是正面向上的概率 有时反面向上更有利于获胜

如果后手投i-1的胜率比先手投i-1的大 那么alice肯定是想要转移到后手投i-1，所以alice此时想投的是正面朝上 ，反之alice希望反面朝上， 如果 g[i−1]>f[i−1]  g [ i − 1 ] > f [ i − 1 ]  

p=p0,q=q0  p = p 0 , q = q 0   否则 p=1−p0,q=1−q0 p = 1 − p 0 , q = 1 − q 0

然后注意到 n=99999999 n = 99999999 过不去

看题解 发现有个trick：题目要求的概率精确到小数点后六位 当 n>1000 n > 1000 时对结果的影响就可以忽略了

所以 f,g f , g 推到 1000 1000 就够了

#include<cstdio>
#include<cstring>
using namespace std;
double f[],g[],p,q;
int T,n,i;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%lf%lf",&n,&p,&q);
        memset(f,,sizeof(f));
        memset(g,,sizeof(g));
        if(n>) n=;
        g[]=;
        for(i=;i<=n;i++){
            if(f[i-]>g[i-])
            p=-p,q=-q;
            f[i]=(p*g[i-]+(-p)*q*f[i-])/(p+q-p*q);
            g[i]=(q*f[i-]+(-q)*p*g[i-])/(p+q-p*q);
            if(f[i-]>g[i-])
            p=-p,q=-q;//要换回来 
        }
        printf("%.6lf\n",f[n]);
    }
    return ;
}