题解 P4550 【收集邮票】

· · 题解

收集邮票

不用数组，直接递推：

我们可以将题目这样理解以下：将每次买到一个新的邮票看成是一个在y=x上的点，其横坐标为这是第几张邮票。

相邻两个点的横坐标是有关系的。设第x个和第x+1个点之间的距离为d，则d服从P(d=v)=(\frac{n-x}{x})^{d-1}(\frac{n-x}{x})的分布。这个式子的意思是为了购买下一张邮票，前d-1次购买邮票没有买到新的，第d次买到了新的。

假设最后一个点的横坐标为X，我们需要求的实际上是\sum_{i=1}^Xi。这是一个阶梯形图形的面积。

在每个点处向右引一条平行于x轴的直线，将这个阶梯图形分为N个梯形。我们可以分别求出每个梯形面积的期望，再累加。因为每个梯形面积的期望显然不会与它的横坐标有关，只跟它是第几个有关。

对于第x个梯形，我们枚举其高，并分别求出它这么高的概率。即：

E_x=\sum_{i=1}^{\infty}(ig_{x-1}+\frac{i(i+1)}{2})\frac{x}{n}(\frac{n-x}{x})^{i-1}

其中g_{x-1}意为剩下的x-1张邮票期望几次买完。由于E与剩下邮票买完的次数是一个线性关系，所以这里可以直接求和。

那么：经过对这个式子的求和(实际上就是三次错位相减)，我们可以求出其极限：

E_x=\frac{ng_{x-1}}{x}+\frac{n^2}{x^2}

然后就是g的求法，显然g_{x}=g_{x-1}+\frac{n}{x}。这是一个经典的问题：一件事情有p的概率成功，求它平均第几次成功。不难算出期望第\frac{1}{p}次成功。

将每个E_x累加就是答案。

于是，代码可以简单地写成：

#include <cstdio>
int n;
double f = 0, g = 0, p;
int main()
{
    scanf("%d", &n);
    for(int x=1; x<=n; ++x)
        p = 1.0 * n / x,
        f += (g += p) * p;
    printf("%.2lf\n", f);
    return 0;
}