SP4060 KPGAME-A game with probability

Alice和Bob在玩一个游戏。

传送门

题意：

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

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

做法：

​ 设$a[i]$为有$i$个石子时Alice先手胜利的概率，$b[i]$为有$i$个石子时Bob先手失败的概率。
$$
a[i]=p\times b[i-1]+(1-p)\times b[i]①
$$

$$
b[i]=q\times a[i-1]+(1-q)\times a[i]②
$$
将$②$带入$①$，
$$
a[i]=\frac{p\times b[i-1]+(1-p)\times q\times a[i-1]}{1-(1-p)\times (1-q)}
$$
同理
$$
b[i]=\frac{q\times a[i-1]+(1-q)\times p\times b[i-1]}{1-(1-q)\times (1-p)}
$$
这里有一个问题，虽然投出正面的人必须取石子，但是$p,q$是指“投出自己想要结果的概率”，所以如果有人发现取走一个硬币会使自己陷入劣势的话，他可以使自己“想投出反面”（这里很简单，大概只有我这个蒟蒻想了好久）。

那么，如果$b[i-1]<b[i]$，Alice或Bob就会选择反面，这里要特判一下。

这样我们得到一个$O(nT)$的做法，到这我就不会做了。

开始无耻的看题解，发现n很大时概率基本不变了（蛤？），那么$n=min(n,233)​$即可。。。

代码:

#include<cstdio>
#include<iostream>
using namespace std;
double a[256],b[256],p,q,p1,q1;
int t,n;
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%lf%lf",&n,&p,&q);
        n=min(n,233); a[0]=0; b[0]=1;
        for (int i=1; i<=n; i++){
            if (a[i-1]>b[i-1]){p1=1-p; q1=1-q;}else{p1=p; q1=q;}
            a[i]=(p1*b[i-1]+(1-p1)*q1*a[i-1])/(1-(1-p1)*(1-q1));
            b[i]=(q1*a[i-1]+(1-q1)*p1*b[i-1])/(1-(1-q1)*(1-p1));
        }
        printf("%.6lf\n",a[n]);
    }
    return 0;
}