「BZOJ 1426」收集邮票【概率与期望】

Time Limit: 1 Sec Memory Limit: 192 MB

Description

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

Input

一个整数 nn

Output

要付出多少钱 (保留两位小数)。

Sample Input

1
3

Sample Output

1
21.25

Constraints

保证 N104N \leqslant 10^4

Solution

注意:买第 ii 次需花 ii 元,而不是标号为 ii 的邮票花 ii 元。

fif_i 表示已经拥有了 ii 张邮票,期望还需要购买的邮票数,则 fn=0f_n = 0

很明显 fi=fiin+fi+1nin+1\displaystyle f_i = f_i \cdot \frac{i}{n} + f_{i+1} \cdot \frac{n-i}{n} + 1

整理得 fi=fi+1+nni\displaystyle f_i = f_{i+1} + \frac {n}{n-i}

gig_i 表示期望还需要的钱。可将这张邮票视为 11 元所买,而后面每张都贵 11 元,故加上 fif_ifi+1f_{i+1}

gi=(gi+1+fi+1)nin+(gi+fi)in+1\displaystyle g_i = (g_{i+1} + f_{i+1}) \cdot \frac{n-i}{n} + (g_i + f_i) \cdot \frac {i}{n} + 1

化简得 gi=gi+1+fi+1+i(ni)fi+nni\displaystyle g_i = g_{i+1} + f_{i+1} + \frac{i}{(n-i)} \cdot f_i + \frac{n}{n-i}

答案即为 g0g_0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

const int maxn = 10010;
double n, f[maxn], g[maxn];

int main() {
scanf("%lf", &n);
for (int i = n - 1; i >= 0; i--) {
f[i] = f[i + 1] + n / (n - i);
}
for (int i = n - 1; i >= 0; i--) {
g[i] = g[i + 1] + f[i + 1] + i / (n - i) * f[i] + n / (n - i);
}
printf("%.2f\n", g[0]);
return 0;
}