这一讲很难很难很难。
讲题人：吴立俊
考虑期望的两个重要性质：
\[E(x)=\sum _i P(x=i) \]这个公式描述了期望和概率的关系。
\[E(x+y)=E(x)+E(y),E(kX)=kE(X) \]这个公式描述了期望的线性性。
那么下面要做一点逆天的事情。
题目描述
有 \(n\) 种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是 \(n\) 种邮票中的哪一种是等概率的，概率均为 \(1/n\)。但是由于凡凡也很喜欢邮票，所以皮皮购买第 \(k\) 次邮票需要支付 \(k\) 元钱。
现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
sol
老师给的题解错误过多，所以我改了一改。
先考虑怎样去计算答案，显然答案是 \(E(\dfrac{m(m+1)}{2})\)，利用期望的线性性，得到 \(ans=\dfrac{1}{2}E(m^2)+E(m).\)
\(E(m)\) 也就是期望步数，可以得到 \(f(x)\) 是已经有 \(x\) 张之后步数的期望。 \(f(i)=1+\dfrac{i}{n} f(i)+\dfrac{n-i}{n} f(i+1).\)
考虑 \(E(m^2).\) 令 \(g(x)\) 为有 \(x\) 张邮票时拿满 \(x\) 张的步数平方期望。
\(p_1(i),p_2(i)\) 分别是 \(x,x+1\) 张时，用 \(i\) 步拿完的概率。显然可以得到以下：
\[f(x)=\sum_i ip_1(i)=E(p_1(i)) \]\[f(x+1)=\sum_iip_2(i) \]\[g(x)=\sum_{i}i^2p_1(i),g(x+1)=\sum_ii^2p_2(i) \]\[p_1(i)=\sum_{j<i}p_2(j)\left(\dfrac{x}{n}\right)^{i-j-1}\times \dfrac{n-x}{n} \]最后一个式子其实有 \(0,1\) 两种决策，这之中的 \(0\) 决策省略。
为什么呢？
首先为了使 \(p_1,p_2\) 关联，你要先取 \(i-j-1\) 次旧的不造成任何贡献，还要取到 \(1\) 张新的也就是 \(\dfrac{n-x}{n}.\) 原因显然。
我们慢慢化简 \(g\) 并且调换 \(i,j\) 的位置可以得到以下：
\[g(x)=\sum _i i^2 \sum_{j<i}p_2(j)\left(\dfrac{x}{n}\right)^{i-j-1}\times\dfrac{n-x}{n} \]再一次化简，
\[g(x)=\dfrac{n-x}{x}\sum_ip_2(i)\sum_{j>i}j^2\left(\dfrac{x}{n}\right)^{j-i} \]然后带入 \(p_1(i)\) 的式子发现 \(f(x)\) 会长成下面的样子：
\[f(x)=\dfrac{n-x}{x}\sum_ip_2(i)\sum_{j>i}j\left(\dfrac{x}{n}\right)^{i-j} \]转而在 \(g\) 式子中枚举 \(j-i\)，可以获得如下：
\[g(x)=\dfrac{n-x}{n}\sum_ip_2(i)\sum_{d=1}^{+\infty}(i+d)\left(\dfrac{x}{n}\right)^d \]考虑利用下面的式子计算 \(p_2\) 的系数：
\[\sum_{i=1}^{+\infty}(a+b)^2A^i=\sum_{i=1}^{+\infty}a^2A^i+\sum_{i=1}^{+\infty}2abA^i+\sum_{i=1}^{+\infty}b^2A^i \]用这个式子和无穷递缩等比数列求和公式并且返回生成函数可以得到如下：
\[g(x)=g(x+1)+f(x+1)+\dfrac{n+x}{n-x}f(x) \]注意到 \(f(x),g(x)\) 分别与 \(f(x+1),g(x+1)\) 有关，所以可以将程序倒序枚举。
程式
#include <bits/stdc++.h>
#define ll long long
#define db long double
using namespace std;
const int N=1e5+10;
db f[N],g[N];
int n;
int main(){
cin>>n;
for(int i=n-1;i>=0;--i) f[i]=f[i+1]+1.0*n/(n-i);
for(int i=n-1;i>=0;--i) g[i]=g[i+1]+f[i+1]+1.0*(n+i)/(n-i)*f[i];
printf("%.2Lf",(f[0]+g[0])/2 );
}