洛谷P1291 [SHOI2002] 百事世界杯之旅 题解

题目链接：P1291 [SHOI2002] 百事世界杯之旅

题意：

假设有 \(n\) 个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？

输入格式：

输入只有一行一个整数，表示不同球星名字的个数 \(n\)。

输出格式：

输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为：

 3
5--
 20

第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的位数。分子和分母的首位都与第一个减号对齐。

分数必须是不可约的。

数据范围：

对于全部的测试点，保证 \(2 \leq n \leq 33\)​。

这道题和 SP1026 FAVDICE - Favorite Dice 基本上是同一道题。

那么这篇题解来讲讲另一种解法吧（其实是另一种推式子的方法）。

设 \(f_i\) 为买到任意 \(i\) 种名字的期望花费，考虑转移 \[ f_i = \frac{i}{n}\cdot f_i + \frac{n - i}{n}\cdot f_{i+1} + 1 \] 解一下方程再化简一下就是 \(f_i = f_{i - 1} + \frac{n}{n - i + 1}\)​ ，答案即 \(f_n\) ，边界 \(f_0 = 0\)​​ 。非常简单。

本题的输出实际上就是求多个数的最小公倍数的问题。

两个数的最小公倍数是 \(t=\frac{ab}{\gcd(a,b)}\) ，三个数就是 \(\frac{tc}{\gcd(t,c)}\) ，以此类推。这个很容易求出来。

时间复杂度 \(\mathcal{O}(n\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define For(i, a, b) for(int i = a, i##END = b; i <= i##END; i++)
#define N ((int)())

int p, q = 1, t;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int cnt(int x, int r = 0) { while(x > 0) ++r, x /= 10; return r; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1; i <= n; i++)
    {
        p = p * i + q * n; q = q * i;
        t = gcd(p, q); p /= t; q /= t;
    }
    t = p / q; p %= q;
    if(p == 0) return cout << t << '\n', 0; 
    For(i, 1, cnt(t)) { cout << ' '; } cout << p << '\n';
    if(t > 0) cout << t;
    For(i, 1, cnt(q)) { cout << '-'; } cout << '\n';
    For(i, 1, cnt(t)) { cout << ' '; }  cout << q << '\n';
    return 0;
}

有意思的是，有的同学可能会推出这样的方程 \[ f_i = \frac{i - 1}{n}\cdot f_i + \frac{n - i + 1}{n}\cdot f_{i-1} + 1 \] 虽然这个方程虽然最后化简出来的是一样的，但是它没有任何意义。

因为如果你想，你甚至可以弄个什么 \(f_i + 114514 = f_{i-1}+\frac{n+1-1}{n-i+1} + 114514\) 出来

我猜，顺推的同学应该是考虑 \(f_{i-1}\) 会如何对 \(f_i\) 贡献，但是不知道 \(f_i\) 会如何对自己贡献，然后凑出来的。