Description#

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

Input#

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

Output#

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

Sample Input#

3

Sample Output#

21.25

题解#

首先考虑每张邮票1元钱，f[i]为当前有i张邮票，要集齐n种邮票的期望花费. $f[i]=i/n*f[i]+(n-i)/n*f[i+1]+1$当花费为k时 g[i]为当前有i张邮票,要集齐n种邮票的期望花费。
我们可以认为买的最后一张邮票的花费为1,倒数第k张的花费为k。 这样 $g[i]=i/n*(g[i]+f[i]+1)+(n-i)/n*(g[i+1]+f[i+1]+1)$化简后就可以O(n)递推了.

1
/*
2
 * @Author: WildRage
3
 * @Date: 2017-06-14 08:15:56
4
 * @Last Modified by: WildRage
5
 * @Last Modified time: 2017-06-14 08:19:55
6
 */
7
#include<iostream>
8
#include<cstdio>
9
using namespace std;
10
double f[10005],g[10005];
11
int main()
12
{
13
    int n;
14
    scanf("%d",&n);
15
    for(int i=n-1;i>=0;i--)f[i]=f[i+1]+(double)n/(n-i);
16
    for(int i=n-1;i>=0;i--)g[i]=(double)i/(n-i)*f[i]+g[i+1]+f[i+1]+(double)n/(n-i);
17
    printf("%.2f",g[0]);
18
}