分析

有一个显然的结论：设当前已经获得的名字个数为 \(k\)，那么再获得其他名字的概率为 \(\frac{n-k}{n}\)。也就是说，平均买 \(n\) 次有 \(n-k\) 个其他的名字，那么再获得一个平均次数为 \(\frac{n}{n-k}\)。

感性理解一下。

事实上有这个定理，对于事件 \(A\)，有 \(P(A)=p\)，那么发生 \(A\) 的期望次数 \(E(A)= \frac{1}{p}\)。

回到题目，就是要求 \(\sum_{i=1}^n \frac{n}{i}\)。要输出为分数形式，那么分别计算分子与分母，最后判断输出就行了。细节见代码。

CODE

#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
int n;
ll p, q, r;
ll gcd(ll x,ll y) { return y? gcd(y,x%y):x; }
int main() {
	scanf("%d",&n);
	p=0, q=1;
    // p是分子，q是分母
	for(int i=1;i<=n;++i) {
		p=p*i+q*n, q*=i;
        // 模拟分数加法，可以自己验证一下
		ll d=gcd(p,q);
        // 及时化简分子分母
		p/=d, q/=d;
	}
	r=p/q, p%=q;
    // r是整数部分，p要去掉r*q这部分
	if(!p) printf("%lld\n",r);
    // 分子是0，表示r是整数
	else {
		int d=log10(r)+1;
        // 整数x的位数=log10(x)+1
		while(d--) printf(" ");
		printf("%lld\n",p);
		d=log10(q)+1;
		if(r) printf("%lld",r);
        // 如果有带分数整数部分，就输出
		while(d--) printf("-"); puts("");
		d=log10(r)+1;
		while(d--) printf(" ");
		printf("%lld\n",q);
	}
}