第一道有关极限期望的数学题，记录一下。
我们设 \(f_i\) 是凑齐前 \(i\) 个球星期望需要买的饮料数。
\[E = 1 \times \dfrac{n - i}{n} + 2 \times \dfrac{i}{n} \times \dfrac{n - i}{n} + 3 \times \left ( \dfrac{i}{n} \right ) ^ 2 \times \dfrac{n - i}{n} + 4 \times \left ( \dfrac{i}{n} \right ) ^ 3 \times \dfrac{n - i}{n} \dots + k \times \left( \dfrac{i}{n} \right ) ^ {k - 1} \times \dfrac{n - i}{n} \]其中 \(k\) 是一个极大数，可以看作是无限，我们由此可以推出下面的式子：
\[\dfrac{i}{n} E = \dfrac{i}{n} \times \dfrac{n - i}{n} + 2 \times \left ( \dfrac{i}{n} \right ) ^ 2 \times \dfrac{n - i}{n} + 3 \times \left ( \dfrac{i}{n} \right ) ^ 3 \times \dfrac{n - i}{n} + 4 \times \left ( \dfrac{i}{n} \right ) ^ 4 \times \dfrac{n - i}{n} \dots + k \times \left( \dfrac{i}{n} \right ) ^ {k} \times \dfrac{n - i}{n} \]相减得：
\[\dfrac{n - i}{n} E = \dfrac{n - i}{n} + \dfrac{i}{n} \cdot \dfrac{n - i}{n} + \left ( \dfrac{i}{n} \right ) ^ 2 \cdot \dfrac{n - i}{n} + \dots + \left ( \dfrac{i}{n} \right ) ^ {k - 1} \cdot \dfrac{n - i}{n} - k \cdot \left ( \dfrac{i}{n} \right ) ^ k \cdot \dfrac{n - i}{n} \]由于 \(k\) 为无限大，所以 \(k \cdot \left ( \dfrac{i}{n} \right ) ^ k \cdot \dfrac{n - i}{n}\) 就无限接近于 \(0\)，所以它对答案的影响也无限接近于 \(0\)，我们可以直接将其省略，那么期望式子就变成这样了：
\[\dfrac{n - i}{n} E = \dfrac{n - i}{n} + \dfrac{i}{n} \cdot \dfrac{n - i}{n} + \left ( \dfrac{i}{n} \right ) ^ 2 \cdot \dfrac{n - i}{n} + \dots + \left ( \dfrac{i}{n} \right ) ^ {k - 1} \cdot \dfrac{n - i}{n} \]将系数化为 \(1\) 得：
\[E = 1 + \dfrac{i}{n} + \left ( \dfrac{i}{n} \right ) ^ 2 + \dots + \left ( \dfrac{i}{n} \right ) ^ {k - 1} \]这里我们可以用等比数列求和公式来做。设 \(S = \dfrac{i}{n} + \left ( \dfrac{i}{n} \right ) ^ 2 + \dots + \left ( \dfrac{i}{n} \right ) ^ {k - 1}\)，则 \(\dfrac{i}{n} S = \left ( \dfrac{i}{n} \right ) ^ 2 + \left ( \dfrac{i}{n} \right ) ^ 3 + \dots + \left ( \dfrac{i}{n} \right ) ^ {k}\)
\[\dfrac{n - i}{n} S = S - \dfrac{i}{n} S = \dfrac{i}{n} - \left ( \dfrac{i}{n} \right ) ^ {k} \]还是考虑极限，\(k\) 为无限大，则 \(\left ( \dfrac{i}{n} \right ) ^ {k}\) 无限接近于 \(0\)，都答案的影响可以忽略不计，所以，
\[\dfrac{n - i}{n} S \approx \dfrac{i}{n}\\ S \approx \dfrac{i}{n - i}\\ E = 1 + S = \dfrac{n}{n - i}\\ \]求出了期望，我们可以写出递推式：\(f_{i + 1} = f_i + \dfrac{n}{n - i}\)，转化一下，就是 \(f_i = f_{i - 1} + \dfrac{n}{n - (i - 1)}\)。
现在，我们可以一步一步的递推过去，也可以将 \(f_i\) 的式子拆开，最后得到 \(f_n = \dfrac{n}{n} + \dfrac{n}{n - 1} + \dots + \dfrac{n}{1} = n \times (\dfrac{1}{1} + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dfrac{1}{5} + \dots + \dfrac{1}{n})\)，两种方法都可以。
//The code was written by yifan, and yifan is neutral!!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
using fs = tuple<ll, ll>;
int n;
ll gcd(ll x, ll y) {
if (y == 0) {
return x;
}
return gcd(y, x % y);
}
fs operator+ (const fs& a, const fs& b) {
ll g = gcd(get<1>(a), get<1>(b));
ll lcm = get<1>(a) / g * get<1>(b);
ll fza = get<0>(a), fzb = get<0>(b);
fza *= (lcm / get<1>(a));
fzb *= (lcm / get<1>(b));
return fs(fza + fzb, lcm);
}
int main() {
n = read<int>();
fs res = fs(1, 1);
rep (i, 2, n, 1) {
res = res + fs(1, i);
}
res = fs(get<0>(res) * n, get<1>(res));
ll num = get<0>(res) / get<1>(res);
if (get<0>(res) % get<1>(res) == 0) {
cout << num << '\n';
return 0;
}
res = fs(get<0>(res) % get<1>(res), get<1>(res));
int digitfz = 0, digitfm = 0, digitps = 0;
ll tmpfz = get<0>(res), tmpfm = get<1>(res), tmpps = num;
ll gc = gcd(tmpfz, tmpfm);
res = fs(get<0>(res) / gc, get<1>(res) / gc);
tmpfz = get<0>(res), tmpfm = get<1>(res), tmpps = num;
while (tmpfz) {
tmpfz /= 10;
++ digitfz;
}
while (tmpfm) {
tmpfm /= 10;
++ digitfm;
}
while (tmpps) {
tmpps /= 10;
++ digitps;
}
int maxx = max(digitfz, digitfm);
rep (i, 1, digitps, 1) {
cout << ' ';
}
cout << get<0>(res) << '\n';
cout << num;
rep (i, 1, maxx, 1) {
cout << '-';
}
putchar('\n');
rep (i, 1, digitps, 1) {
cout << ' ';
}
cout << get<1>(res) << '\n';
return 0;
}