题目链接戳这里
首先递归调用函数次数其实是可以预处理出来的，但是这里我们介绍一个更屌的做法。
设\(F(i,j)\)为求解\(P(i,j)\)所遍历的节点数目，则有$$F(0,j)=F(i,0)=0$$
\[F(i,j)=F(i-1,j)+F(i,j-1)+2
\]
\]
我们观察一下，发现这个式子与组合恒等式$$\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}$$
于是我们可以令\(G(i,j)=F(i,j)+2\)，则有$$G(i,j) = G(i-1,j)+G(i,j-1)$$
再通过待定系数便可以得到$$F(i,j)=2\binom{i+j}{i}-1$$
下面考虑\(P(i,j)\)的求法，我们可以枚举起始点\((0,a)\)（就是枚举递归边界），则这个点对答案的贡献即为$$\binom{i+j-a-1}{j-a}p{i}(1-p){j-a}$$
这个可以画一个格点图来考虑。
那么算法我们分析完了，接下来就是这道题最蛋痛的地方了——高精度。我开始C++为了不写除法特意采用了质因子合并的算法，并且还保证了复杂度。但是，玩玩没想到算\(P(i,j)\)的时候double的精度不够，可能要用取对数的思想，但我不想想了。于是便将目光转向java，BigDecimal类精度绝对够了。下面就是我的代码：
import java.math.*;
import java.util.*;
public class Main
{
static final int num = 2010;
static BigInteger C[][] = new BigInteger[num][num];
public static void main(String args[])
{
for (int i = 0;i < num;++i) for (int j = 0;j < num;++j) C[i][j] = BigInteger.ZERO;
for (int i = 0;i < num;++i)
{
C[i][0] = BigInteger.ONE;
for (int j = 1;j <= i;++j) C[i][j] = C[i-1][j-1].add(C[i-1][j]);
}
Scanner cin = new Scanner(System.in); BigDecimal P,Q; int Case = 0;
while (true)
{
P = cin.nextBigDecimal(); Q = (BigDecimal.valueOf(1)).subtract(P);
int N = cin.nextInt(); if (N == 0) break;
if (Case++ > 0) System.out.println("");
while ((N--) > 0)
{
int a = cin.nextInt(),b = cin.nextInt();
if (a <= 0&&b <= 0) System.out.println("-1.00000\n0");
else if (a < 0||b < 0) System.out.println("-1.00000\n0");
else if (a > 1000||b > 1000) System.out.println("-1.00000\n0");
else
{
BigDecimal sum = new BigDecimal(0);
if (a == 0) sum = BigDecimal.valueOf(1);
else for (int i = 1;i <= b;++i) sum = sum.add(new BigDecimal(C[a+b-i-1][a-1]).multiply(P.pow(a).multiply(Q.pow(b-i))));
System.out.format("%.5f\n",sum);
System.out.println(C[a+b][a].multiply(BigInteger.valueOf(2)).subtract(BigInteger.valueOf(2)));
}
}
}
}
}