2011-0003

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

设f(k)为变为k个吸血鬼的期望的天数，p(k)为k个吸血鬼变为k+1个吸血鬼的概率，那么则f(1)即为题目所求，并且有：

p(k) = k * (n - k) * p / C(n, 2)

f(n) = 0

f(k) = f(k) * (1 - p(k)) + f(k+1) * p(k) + 1

f(k) = f(k+1) + 1 / p(k)

f(1) = f(1) - f(2) + f(2) - f(3) + ... + f(n-1) - f(n) + f(n)

f(1) = 1 / p(1) + 1 / p(2) + ... + 1 / p(n) + f(n)

f(1) = C(n, 2) * sigma(1 / (k * (n - k))) / p    (k:0->n-1)

f(1) = (n - 1) / 2 * sigma(1 / k + 1 / (n - k)) / p

f(1) = (n - 1) * sigma(1 / k) / p

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 100086;
double f[MAXN];

int main() {
    int i, j, k;
    int m, n;
    int tc;
    double p;

    for (i=1; i<MAXN; ++i) f[i] = f[i-1] + 1.0 / i;
    scanf("%d", &tc);
    while (tc--) {
        scanf("%d %lf", &n, &p);
        printf("%.3lf\n", (n-1)*f[n-1]/p);
    }
    return 0;
}
}}}
[by delta_4d]

设f(k)为变为k个吸血鬼的期望的天数，p(k)为k个吸血鬼变为k+1个吸血鬼的概率，那么则f(1)即为题目所求，并且有：

p(k) = k * (n - k) * p / C(n, 2)

f(n) = 0

f(k) = f(k) * (1 - p(k)) + f(k+1) * p(k) + 1

f(k) = f(k+1) + 1 / p(k)

f(1) = f(1) - f(2) + f(2) - f(3) + ... + f(n-1) - f(n) + f(n)

f(1) = 1 / p(1) + 1 / p(2) + ... + 1 / p(n) + f(n)

f(1) = C(n, 2) * sigma(1 / (k * (n - k))) / p (k:0->n-1)

f(1) = (n - 1) / 2 * sigma(1 / k + 1 / (n - k)) / p

f(1) = (n - 1) * sigma(1 / k) / p

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100086;
double f[MAXN];
int main() {
    int i, j, k;
    int m, n;
    int tc;
    double p;
    for (i=1; i<MAXN; ++i) f[i] = f[i-1] + 1.0 / i;
    scanf("%d", &tc);
    while (tc--) {
        scanf("%d %lf", &n, &p);
        printf("%.3lf\n", (n-1)*f[n-1]/p);
    }
    return 0;
}

[by delta_4d]