题目描述
“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不赶快行动！”
你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？
输入格式
整数n（2≤n≤33），表示不同球星名字的个数。
输出格式
输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为（复制到记事本）： $5 \frac{3}{20}$
第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。
分数必须是不可约的。
输入样例
2
输出样例
3
Solution
首先，我们可以用 $f[n][k]$ 来表示一共有 $n$ 个球星还剩下 $k$ 个球星没有收集到，依此我们可以推出一个方程：
然后经过一些变换：
但这样计算太麻烦了，所以又经过一系列玄学操作，就变成了：
（虽然还是很难计算）
以上，就是对本题的推导。
最后，我还要说一句：
光是是输出就调了好长时间。
如果是输出小数的话我早就A了
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <cstdio>
#define ll long long
ll gcd(ll a , ll b) {
if (b == 0) return a;
else return gcd(b , a % b);
}
ll lcm(ll a , ll b) {
return a * b / gcd(a , b);
}
ll n , ans , ws1 = 0 , ws2 = 0 , fm = 1 , fz = 0 , yfz = 1 , d = 0 , k , r;
int main() {
scanf("%lld" , &n);
for (ll i = 1 ; i <= n ; i++) {
fz = fz * i + fm * n;
fm *= i;
r = gcd(fm , fz);
fm /= r;
fz /= r;
}
r = fz / fm;
if (fm == 1) {
printf("%lld" , fz);
}
else {
ll y = r;
while (y != 0) {
y /= 10;
ws1++;
}
ll fmn = fm;
while (fmn != 0) {
fmn /= 10;
ws2++;
}
for (ll i = 1 ; i <= ws1 ; i++) {
printf(" ");
}
printf("%lld" , fz % fm);
puts("");
printf("%lld" , r);
for (ll i = 1 ; i <= ws2 ; i++) {
printf("-");
}
puts("");
for (ll i = 1 ; i <= ws1 ; i++) {
printf(" ");
}
printf("%lld" , fm);
}
return 0;
}
|
