题目链接

题解

记$f[i]$表示Alice胜的概率，$g[i]$表示Bob胜的概率，$a$表示Alice抛出正面的概率，$b$表示Bob抛出正面的概率，则：

$$\begin{gathered} f[i]=a\times g[i-1]+(1-a)\times g[i] \\ g[i]=b\times f[i-1]+(1-b)\times f[i] \end{gathered}$$

化简得到

f[i]=a×g[i−1]+(1−a)×b×f[i−1]a+b−a×bg[i]=b×f[i−1]+(1−b)×a×g[i−1]a+b−a×b f[i]=\frac{a\times g[i-1]+(1-a)\times b\times f[i-1]}{a+b-a\times b}\\ g[i]=\frac{b\times f[i-1]+(1-b)\times a\times g[i-1]}{a+b-a\times b} f[i]=a+b−a×ba×g[i−1]+(1−a)×b×f[i−1]​g[i]=a+b−a×bb×f[i−1]+(1−b)×a×g[i−1]​

可以看出，当$f[i-1]>g[i-1]$时，$a=1-p,b=1-q$，否则$a=p,b=q$。初值$f[0]=0,g[0]=1$

但是$O(n)$的转移显然会TLE，事实上，当$n$很大时，概率几乎不再改变，因此当$n>100$时可以认为$n=100$。

代码

#include 
    
     #include 
     
      const int maxn=100;int t,n;double p,q,f[maxn+10],g[maxn+10];int main(){
      scanf("%d",&t);  while(t--)    {
          scanf("%d%lf%lf",&n,&p,&q);      f[0]=0;      g[0]=1;      n=std::min(n,maxn);      for(int i=1; i<=n; ++i)        {
              double a,b;          if(f[i-1]>g[i-1])            {
                  a=1-p;              b=1-q;            }          else            {
                  a=p;              b=q;            }          f[i]=(a*g[i-1]+(1-a)*b*f[i-1])/(a+b-a*b);          g[i]=(b*f[i-1]+(1-b)*a*g[i-1])/(a+b-a*b);        }      printf("%.6lf\n",f[n]);    }  return 0;}