吸血鬼，挺有意思的，概率数列题。

村子里有 n-1 个人，1 个吸血鬼，每天随机抽取两个家伙进行反应，如果是一个人一个鬼，那么有 p 的概率会把人变成吸血鬼，求全部变成吸血鬼的期望天数。

分析一下，假设 n, p 为常数 E(k) 为有 k 只吸血鬼的期望天数，不难发现，其实从 E(k) 到 E(k+1) 有一个直接的递推关系。

初始值，E(1) = 0，现在要求 E(n)。

然后我们说一下这个递推关系：

1. 如果有 k 只鬼，那么每个晚上可以变成 k+1 只鬼的概率是：

q = p*k*(n-k)/c(n,2) = 2*p*k*(n-k)/n/(n+1)

1. 然后有：

E(k+1) = E(k) + 1*q + 2*q*(1-q) + 3*q*(1-q)^2 + ...

1. 对于上式右侧的数列，高中的时候学过，可以这样解：

设：

s = q * (1 + 2*(1-q) + 3*(1-q)^2 + ...)

则：

(1-q)*s = q * (0 + (1-q) + 2*(1-q)^2 + ...)

两式相减得到：

s * q = q * (1 + (1-q) + (1-q)^2 + (1-q)^3 + ...)

这是一个等比数列的所有项和，因此：

s = 1 / q

多么优美的结果，也就是说：

E(k+1) = E(k) + 1/q

所以，我们将 k 从 1 遍历到 n-1，求出对应的 1/q，累加起来，就得到了结果。

// 3493567 2013-12-21 18:16:02 Accepted 3551 C++ 90 168 呆滞的慢板

#include <cstdio>

int main() {

    int t, n, k;
    double p, ans;

    for(scanf("%d", &t); t--;) {
        scanf("%d%lf", &n, &p);
        for(ans = 0, k = 1; k < n; ++k)
            ans += 1.0/k/(n-k);
        printf("%.3lf\n", 0.5*n*(n-1)/p*ans);
    }

}

---

【转载请附】愿以此功德，回向 >>

原文链接：http://www.huangwenchao.com.cn/2013/12/zoj3551.html【zoj 3551 – Bloodsucker】