两个人 A, B 取 n 枚石子，祂们轮流抛硬币 (A 先手)，每次抛硬币，如果是正面，就取出一枚石子，否则什么都不做，然而 A, B 有一种超能力，在抛硬币前在意志中确定一面 (正面或反面)，然后就有 pA 或 pB 的概率抛出意志中的那一面 (当然，常人的 p = 0.5)。取得最后一枚石子的人获胜。假如 A, B 都采取最佳策略，求 A 获胜的概率，其中 pA, pB ≥ 0.5，n ≤ 108，精度 6 位小数。

　　这道题好难啊。。用全概率公式做。

　　设$f_i$为剩下i枚石子，A先手，A获胜的概率。$g_i$为剩下i枚石子，B先手，A获胜的概率。显然$f_0=0$，$g_0=1$。

　　令事件X表示剩下i枚石子，A先手且获胜。事件Y表示剩下i枚石子，A抛硬币抛到正面。显然硬币只有两面，所以$A$和$\overline{A}$是$\Omega$的完备事件组。

　　因为如果抛到正面，那么A获胜的概率就是有i-1枚棋子，B先手，A获胜的概率，所以：$p(X\mid Y)=g_{i-1}$，$p(X\mid Y)=g_i$。那么根据全概率公式$p(X)=p(X\mid Y)p(Y)+p(X\mid \overline Y)p(\overline Y)=p(Y)g_{i-1}+p(\overline Y)g_i$。p(Y)是A抛到正面的概率，也就是要根据A想不想抛到正面来改变。暂时记$p(Y)=P_{A'}$，则$f_i=p(X)=P_{A'}g_{i-1}+(1-P_{A'})g_i$。同理，$g_i=P_{B'}f_{i-1}+(1-P_{B'})f_i$。然后联立方程组（我们要让方程组里不包含下标为i的东西，这是dp的原则），可得：$$f_i=\frac{P_{A'}g_{i-1}+(1-P_{A'})P_{B'}f_{i-1}}{P_{A'}+P_{B'}-P_{A'}P_{B'}}$$

　　那么现在来考虑$P_{A'}$和$P_{B'}$。来看$P_{A'}$。明显，如果$g_{i-1}>g_i$，代入一下前面$g_i$的等式，可得如果$f_{i-1}<g_{i-1}$，A想抛正面（算一算，很凑巧），所以$P_{A'}=p(A)$。$f_{i-1}>g_{i-1}$时A想抛反面，所以$P_{A'}=1-p(A)$，同理也可以推出$P_{B'}$的。

1 #include 
     
       2 using namespace std; 3  4 const int maxn=1e6+5; 5 int t, n; 6 double f[maxn], g[maxn]; 7 double pa, pb, panow, pbnow, tmp; 8  9 int main(){10     scanf("%d", &t);11     for (int tt=0; tt
      
       1e6) n=1e6;14         f[0]=0, g[0]=1;15         for (int i=1; i<=n; ++i){16             if (f[i-1]!=g[i-1]){17                 if (f[i-1]