[SHOI2002]百事世界杯之旅

題目：“……在2002年6月之前購買的百事任何飲料的瓶蓋上都會有一個百事球星的名字。只要湊齊所有百事球星的名字，就可參加百事世界杯之旅的抽獎活動，獲得球星背包，隨聲聽，更克赴日韓觀看世界杯。還不趕快行動！”

你關上電視，心想：假設有n個不同的球星名字，每個名字出現的概率相同，平均需要買幾瓶飲料才能湊齊所有的名字呢？

輸入\(n(2\le n\le33)\)，以帶分數or整數的形式輸出購買的期望數。

令\(f[i]\)代表集齊\(i\)個明星需要的瓶蓋數量。我們很容易得到

\(\displaystyle f[i]=\frac{i-1}{n}f[i]+\frac{n-i+1}{n}f[i-1]+1\)

然后這個式子不清真，因為\(f[i]\)的遞推式里有\(f[i]\)遞推個蛋啊，所以對\(f[i]\)移項

\(\displaystyle \frac{n-i+1}{n}f[i]=\frac{n-i+1}{n}f[i-1]+1\)

然后再搞搞

\(\displaystyle f[i]=f[i-1]+\frac{n}{n-i+1}\)

行了，這是一個遞推式的形式，完美。。。。。

所以\(\displaystyle f[n]=\sum_{i=1}^n\frac{n}{n-i+1}=\sum_{i=1}^n\frac{n}{i}\)

行了，這就完美了。。。

然后呢我們就給他加加加哎哎哎家家愛阿基愛家啊啊

自己寫一個分數的結構體搗鼓就行了

最后輸出的時候，為了安全我多寫了點，如代碼：

如果這個代碼沒有成功地高亮顯示，說明你在瀏覽某LJ網站，請自覺的點我。拒絕lj網站從我做起

#include <bits/stdc++.h>
using namespace std;
#define int long longint getlen(long long x, bool mode)
{if(mode == 1 && x == 0)return 1;int ans = 0;while (x > 0){ans++;x/= 10;}return ans;
}struct fraction
{long long son, mother;fraction(int son = 0, int mother = 1) : son(son), mother(mother){}void redution(){int g = __gcd(mother, son);mother /= g;son /= g;}void print(){redution();long long div = son / mother;long long rest = son % mother;if (rest == 0){printf("%lld\n", div);return;}int len = getlen(div, 0);int len1 = getlen(rest, 1);int len2 = getlen(mother, 1);int len3 = max(len1, len2);for (int i = 1; i <= len; i++)putchar(' ');printf("%lld\n", rest);if (div > 0)printf("%lld", div);for (int i = 1; i <= len3; i++)putchar('-');printf("\n");for (int i = 1; i <= len; i++)putchar(' ');printf("%lld\n", mother);}}; fraction operator+(const fraction &a, const fraction &b)
{fraction ans(a.son * b.mother + a.mother * b.son, a.mother * b.mother);ans.redution();return ans;
}signed main()
{int n; scanf("%lld", &n);fraction ans;for (int i = 1; i <= n; i++){fraction tmp(n, i);ans = ans + tmp;}ans.print();return 0;
}