先考虑一下如果我想赢得游戏，我会采取的最优策略是什么。
首先，想赢得游戏就是要取到最后一个石子，每次抛硬币相当于给你一次机会，每次机会都有相同概率取到石子，显然，最优策略就是让我最后一次取石子的机会越多。
如何让机会最多？当然是取最后一个石子时，我先抛硬币，这样我的机会就越多。也就是说，我不想取倒数第二个石子。因为如果是我取了倒数第二个石子的话，取最后一个石子时先抛硬币的就是对手了。
那么就可以考虑 dp 了：设 \(dp(i,j=0/1,k=0/1)\) 表示 Alice 和 Bob 都 想（\(k=0\)）/不想（\(k=1\)） 取到第 \(i\) 个石子，最后 Alice（\(j=1\)）/Bob（\(j=2\)） 实现愿望的概率。（实现愿望就是指“取到（\(k=0\)）/没取到（\(k=1\)） 第 \(i\) 个石子”）。
接下来以 \(dp(i,j,0)\) 的转移为例：表示两个人都想要取到第 \(i\) 个石子，最后 \(j\)（代表 Alice 或 Bob）取到的概率。
显然，两个人的最优策略都是他们都想先抛第 \(i\) 个石子的硬币。意思就是说他们都不想取第 \(i-1\) 个石子。
-
假设 \(j\) 成功地没取到第 \(i-1\) 个石子，那么有：（其中设 \(p[0]=p\)，\(p[1]=q\)）
\[\begin{aligned}dp(i,j,0)=&dp(i-1,j,1)\times p_j \times\\&\{1+\underbrace{(1-p_j)(1-p_{j\oplus1})}_{\text{第一轮两人都没扔到正面的概率}}+\underbrace{[(1-p_j)(1-p_{j\oplus1})]^2}_{\text{前两轮两人都没扔到正面的概率}}+\underbrace{[(1-p_j)(1-p_{j\oplus1})]^3}_{\text{前三轮两人都没扔到正面的概率}}+\dots\}\end{aligned} \]最后面那个括号里的东西有点复杂，考虑化简：
令 \(t_0=(1-p_j)(1-p_{j\oplus1})\)，令
\[\begin{aligned}S_0&=\lim_{k\rightarrow \infty}1+t_0+t_0^2+\dots+t_0^k\\S_0t_0&=\lim_{k\rightarrow \infty}t_0+t_0^2+\dots+t_0^{k+1}\end{aligned} \]上式减下式得：
\[\begin{aligned}S_0(1-t_0)&=\lim_{k\rightarrow \infty}1-t_0^{k+1}\\S_0&=\frac{\lim_{k\rightarrow \infty}1-t_0^{k+1}}{1-t_0}\\&=\frac{1-0}{1-t_0}(0<t_0<1\text{ 得}\lim_{k\rightarrow \infty}t_0^{k+1}=0)\\&=\frac{1}{1-t_0}\end{aligned} \]那么就有：\(dp(i,j,0)=dp(i-1,j,1)\times p_j\times S_0\)。
-
假设 \(j\) 没能成功地不取第 \(i-1\) 个石子，也就是说他不幸地取到了第 \(i-1\) 个石子，那么必须得先让对手取一次，再轮流取，即：
\[dp(i,j,0)=\underbrace{[1-dp(i-1,j,1)]}_{\text{上次没成功的概率}}\times \underbrace{(1-p_{j\oplus1})}_{\text{对手第一次抛硬币没扔到正面的概率}}\times\underbrace{p_j\times S_0}_{\text{接下来轮流抛，$j$ 抛到正面的概率}} \]
综述，可以推出：
\[dp(i,j,0)=dp(i-1,j,1)\times p_j\times S_0+[1-dp(i-1,j,1)]\times(1-p_{j\oplus1})\times p_j\times S_0 \]自己按上面的方法推一下，同理可得：
\(dp(i,j,1)=dp(i-1,j,0)\times (1-p_{j\oplus 1})\times S_1+[1-dp(i-1,j,0)]\times p_j\times (1-p_{j\oplus 1})\times S_1\)
（其中 \(S_1=\frac{1}{1-t_1}\)，\(t_1=p_j\times p_{j\oplus1}\)）
按这种方法 dp（要滚动一下），发现时间复杂度是 \(O(n)\) 的，过不去。
猜测用矩阵快速幂加速或者有收敛，手测了几组大数据之后发现有收敛，于是就过了。（当然用矩阵快速幂应该也可以）
代码如下：
#include<bits/stdc++.h>
using namespace std;
int t,n;
double p[2],dp[2][2][2];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%lf%lf",&n,&p[0],&p[1]);
n=min(n,1000);//收敛
double s[2];
s[0]=(1-(1-p[0])*(1-p[1]));
s[1]=(1-p[0]*p[1]);
memset(dp,0,sizeof(dp));
dp[0][0][1]=dp[0][1][0]=1;
int now=1;//滚动数组（其实收敛之后不用滚动都可以）
for(int i=1;i<=n;i++,now^=1)
{
for(int j=0;j<2;j++)
{
dp[now][j][0]=dp[now^1][j][1]*p[j]/s[0]+(1-dp[now^1][j][1])*(1-p[j^1])*p[j]/s[0];
dp[now][j][1]=dp[now^1][j][0]*(1-p[j^1])/s[1]+(1-dp[now^1][j][0])*p[j]*(1-p[j^1])/s[1];
}
}
printf("%lf\n",dp[now^1][0][0]);
}
return 0;
}