Description：

每次等概率获得一个 $1$ ~ $n$ 之间的数字，问期望多少次获得所有数字。

$1\le n \le 33$

Solution：

倒序转移，设 $f[i]$ 表示 $i$ 及之后都集齐了的期望， $f[n+1]=0$ ，那么对于当前 $i$ ， $f[i+1]$ 有 $\frac i n$ 的概率转移到他， $f[i]$ 有 $\frac{n-i}n$ 的概率转移到他，即 $f[i]=\frac i n(f[i+1]+1)+\frac{n-i}n(f[i]+1)$ ，移个项就是 $f[i]=f[i+1]+\frac n i$

封装一个 $frac$ 结构体即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

#define MAXN 50

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

struct frac

{

	ll x,y;

	frac(ll x_ = 0,ll y_ = 1){ll t = gcd(x_,y_);x = x_ / t;y = y_ / t;}

	friend frac operator + (frac a,frac b)

	{

		frac res;

		res.y = a.y * b.y;

		res.x = a.x * b.y + b.x * a.y;

		ll t = gcd(res.x,res.y);

		res.y /= t;res.x /= t;

		return res;

	}

}f[MAXN];

ll cnt(ll k)

{

	ll res = 0;

	while(k > 0)

	{

		k /= 10;

		++res;

	}

	return res;

}

int main()

{

	scanf("%lld",&n);

	for(ll i = n;i >= 1;--i)

	{

		f[i] = f[i + 1] + (frac){n,i};

	}

	if(f[1].y == 1)

	{

		cout << f[1].x << endl;

	}

	else

	{

		ll ans = 0;

		while(f[1].x > f[1].y)

		{

			++ans;

			f[1].x -= f[1].y;

		}

		ll l = cnt(ans);

		for(ll i = 1;i <= l;++i)putchar(' ');

		cout << f[1].x << endl;

		cout << ans;

		l = cnt(f[1].y);

		for(ll i = 1;i <= l;++i)putchar('-');

		cout << endl;

		l = cnt(ans);

		for(ll i = 1;i <= l;++i)putchar(' ');

		cout << f[1].y << endl;

	}

	return 0;

}