SP1026 FAVDICE - Favorite Dice

题意：

有个 $n$ 面的骰子，要求每一面都掷到，期望掷多少次。

题解：

赠券收集问题。

假设手上已经有了 $i - 1$ 个面，从集合中选取一个新的面的概率为 $\frac{n - i + 1}n$ ，那么期望就是 $\frac n {n - i + 1} $。

总期望为 $\sum_{i = 1} ^n \frac n {n - i + 1} = \sum _{i = 1} ^ n \frac n i$。

为什么会是倒数呢？有一个硬币，有 $\frac 12$ 的概率取到正面，那么取到正面的期望次数就是 $2$。（迷惑）

也可以用dp 来推。

我们设 $f_i$ 表示已经取了 i 种数到达取 $n$ 种数的次数的期望。

显然有 $f_i = 0$ ,所以需要逆推。

选择 $i$ 种数之后, 再选一个数，与之前相同的概率 $\frac i n$，不同的概率为 $\frac{n - i} n$，本次取到数的期望W为 1，

所以， $f_i = \frac {n - i} n f_{i + 1} + \frac i n f_i + 1$。

化简可以得到， $f_i = f_{i + 1} + \frac n{n - i}$。

有几个疑惑：

$\frac {n - i} n$ 表示的是概率， $f_{i + 1}$ 表示的是期望，为什么概率可以和期望去相乘？

因为$f_i$ 表示的是已经取了 i 种数到达取 $n$ 种数的次数的期望，所以在这里它就相当于权值。
最后为啥要加 1 ？

仍然是从 $f_i$ 的定义上去理解，因为$f_i$ 表示已经取了 i 种数到达取 $n$ 种数的次数的期望。

不论它取到了新的，还是没有取到新的，它这一次是一定要取的，所以取的次数加 1。

感性理解一下吧！

感谢 https://www.luogu.com.cn/blog/pufanyi/solution-sp1026

/*
Date:2021.9.6
Source:SP1026
konwledge:期望dp 
*/
#include <iostream>
#include <cstdio>
#define orz cout << "AK IOI" << "\n"

using namespace std;
const int maxn = 1010;

inline int read()
{
	int f = 0, x = 0; char ch = getchar();
	while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 + '0');
}
int T, n;
double f[maxn]; 
int main()
{
	//freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	T = read();
	while(T--)
	{
		n = read();
		f[n] = 0;
		for(int i = n - 1; i >= 0; i--) 
			f[i] = f[i + 1] + n / (double)(n - i);
		printf("%.2lf\n", f[0]);
	}
	return 0;
}

SP1026 FAVDICE - Favorite Dice

SP1026 FAVDICE - Favorite Dice

推荐阅读