问题 C: 【概率】百事世界杯之旅

题目描述
“…在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可以参加百事世界杯之旅的抽奖活动，获取球星背包、随身听，更可以赴日韩观看世界杯。还不赶快行动！…”
你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？
输入
输入一个整数n，2≤n≤33，表示不同球星名字的个数。
输出
输出凑齐所有的名字平均需要购买的饮料瓶数。如果是一个整数，则直接输出，否则用下面样例中的格式分别输出整数部分和小数部分。分数必须是不可约的。先输出整数部分，若有小数部分，用括号把不可约分式括起来。
样例输入 Copy
2
样例输出 Copy
3
提示
如果输入5，则输出11(5/12)

下面是递推过程：
公式为f(n , k) = f(n , k - 1) + n / k
设f(n , k) 为在n种不同的饮料中选取还剩下k个未选的，所需要的购买的平均饮料瓶数 ， 根据全期望公式 , f(n , k) = （这一次没选中新的概率） * f(n , k) + (这一次选中新的概率) * f(n , k - 1) + 1 （当n == k时 ， f（n , n）表示一个还没选，这个时候随便选一个新的概率为1）
即f(n , k) = (n - k ) / n * f(n , k) + k / n * f(n , k - 1) + 1
然后进行这个公式的处理就行了

#include <bits/stdc++.h>
#pragma GCC optimize(3 , "Ofast" , "inline")
using namespace std;
typedef long long ll ;
const int INF = 0x3f3f3f3f ;
const int N = 1e5 + 10 ;
int main()
{
   int n  ;
   cin >> n ;
   ll a = 1 , b = 1 ;
   for(int i = 2; i <= n ;i ++)
    {
    	a = a * i + b , b = i * b ;
    	ll d = __gcd(a , b) ;
    	a /= d , b /= d ;
	}
	a *= n ;
	if(a % b == 0) 
	 cout << a / b << endl ;
	else 
	 {
	 	cout << a / b ;
	 	a = a - a / b * b ;
	 	ll d = __gcd(a , b) ;
	 	cout << "(" << a / d << "/" << b / d << ")"<< endl ;
	 }
   return 0 ;
}