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