BZOJ 1426: 收集邮票

1426: 收集邮票

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 317  Solved: 253
[Submit][Status][Discuss]

Description

有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。

Input

一行,一个数字N N<=10000

Output

要付出多少钱. 保留二位小数

Sample Input

3

Sample Output

21.25

HINT

 

Source

 

[Submit][Status][Discuss]

好水啊，太水了，不能再水了~~~~

先求出收集到i种邮票的期望购买次数，设$x$为买第i种时每次购买和之前重复的概率，$x=frac{i-1}{n}$，那么买到i的期望次数就是$1+x+x^2+...=frac{1}{1-x}$ 很简单╮(￣▽￣")╭

然后考虑每次买的代价，买i时，可以认为之前已经购买过$a_{i-1}$次，那么新的购买代价就是$a_{i-1}+1$，需要本次购买的概率是1，而下次购买的代价是$a_{i-1}+2$，概率是$frac{1}{x}$，对这个东东求和到正无穷项就好了。

然后写个暴力对这个东东求和到第100000次项，发现可以过掉1000以内的所有数据，大概是没问题了。

然后这东西本身就是个等差乘等比，算一下求和公式，就知道加到正无穷的和是多少了，然后就可以O(1)回答这个问题，总的时间复杂度是O(N)的。

#include <cstdio>

const int siz = 10005;

int n;

double a[siz];
double b[siz];

inline double calc(double p, double k)
{
    double t = 1.0 / (1 - k);
    
    return ((p + 1) + t - 1) * t;
}

signed main(void)
{
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i)
        a[i] = a[i - 1] + 1.0 * n / (n - i + 1);
        
    b[1] = 1;
    
    for (int i = 2; i <= n; ++i)
        b[i] = b[i - 1] + calc(a[i - 1], 1.0 * (i - 1) / n);
        
    printf("%.2lf
", b[n]);
}

@Author: YouSiki