设E(k)为有k只吸血鬼时的期望天数,则E(1) = 0,我们试着从E(k)推出E(k+1):

  1. k只吸血鬼过一天变成k+1只吸血鬼的概率
  2. 知道一天就变成k+1只吸血鬼的概率q后,两天变成k+1只吸血鬼的概率就为,三天则是,……(几何分布)
  3. 所以 右边那一串为几何分布的期望,其值为(具体计算过程就不写了,见这篇文章) 从而 所以
/*90ms,168KB*/

#include <cstdio>

int main()
{
    int t, n, k;
    double p, ans;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%lf", &n, &p);
        ans = 0.0;
        for (k = 1; k < n; ++k) ans += 1.0 / k / (n - k); // 可以折半算,最后*2
     printf("%.3f\n", 0.5 * n * (n - 1) / p * ans);
    }
    return 0;
}

Comments

comments powered by Disqus