LightOJ - 1408 Batting Practice 公式 ＋ 概率

题目大意：有一个人在投篮，投不进的概率为p。现在他要玩一个游戏，如果连续投中m颗球或者连续投不进n颗球，那么就停止投篮
现在问，他停止投篮的期望是多少

解题思路：设g[i]为已经投中了i颗，还需要投进m-i颗球的期望，设f[i]为投丢了i颗，还需要再投丢n－i颗球的期望，那么可得公式
g[i] = (1-p) * (g[i+1] + 1) + p * (f[1] + 1),即
g[i] = (1-p) * g[i+1] + f[1] + 1
f[i]和g[i]的公式相似，这里就不写了
观察g的公式可得，最后的g[1] = (1-p)^(k-1) * (p f[1] + 1) + (1 - p) ^(k-2) (p * f[1] + 1) + … + (1-p)^0 * (f[1] + 1)，即可得到一个等比数列的求和公式，f[1]也可由这个得到
现在假设q = 1 - p, k1 = q ^(m-1) + q ^ (m-2) + … + q ^ 0,k2 = p ^ (n - 1) + … + p ^ 0
那么g[1] = k1 * (p * f[1] + 1) , f[1] = k2 * (q * g[1] + 1)
由这两个公式可求得g[1]和f[1]
得到这两个后即可得到答案q * (g[1] + 1) * p (f[1] + 1)

#include<cstdio>
#include<cmath>
using namespace std;
double esp = 1e-9;

int main() {
    int test, in, out, cas = 1;
    double p;
    scanf("%d", &test);
    while(test--) {
        scanf("%lf%d%d", &p, &in, &out);
        if(p < esp) {
            printf("Case %d: %d\n", cas++, in);
            continue;
        }
        if(1.0 - p < esp) {
            printf("Case %d: %d\n", cas++, out);
            continue;
        }   
        double q = 1.0 - p;
        double k1 = 1.0 - pow(q, in - 1);
        double k2 = 1.0 - pow(p, out -1);
        k1 = k1 / p;
        k2 = k2 / q;
        double f = ((k1 * k2 * p) + k1) / (1.0 - k1 * k2 * p * q);
        double g = k2 * (q * f + 1.0);
        double ans = q * f + p * g + 1.0;
        printf("Case %d: %lf\n",cas++,ans);
    }
    return 0;
}