under 题解 UVA10288

---

乍看这题：这不是裸的概率 dp 吗！

直到我看到输出格式……

为啥要输出带分数啊 自闭了，怎么代码比推导难啊

---

自闭归自闭，题目还是要做的。根据 数学直觉 这道题的经验，我们知道答案应该是 $\ n\sum_{i = 1}^n \tfrac{1}{i} \ $（这道题难点不在这个结论，就不进行证明了）。

要输出分数，调和级数 $ ( \sum_{i = 1} \frac{1}{i} ) $ 求起来就没有那么快乐了。我们假设已经求出调和级数的前 $i - 1 \ (i > 1)$ 项是 $\frac{a}{b}$，那么第 $i$ 项就是

$$\frac{a}{b} + \frac{1}{i} = \frac{ai + b}{bi}$$

一个简单的通分，使得这题可以直接计算了。

初看式子，我以为会爆精度。（由于并不会处理未知组数数据）打算用 python 打表，写出了这段代码 (python3)：

from math import gcd

A = [0, 1]
B = [0, 1]

for i in range(2, 34): # [2, 34)
  a = A[-1]
  b = B[-1]
  A.append(a * i + b)
  B.append(b * i)
  d = gcd(A[-1], B[-1])
  A[-1] //= d
  B[-1] //= d

for i in range(1, 34):
  print('{} {}'.format(A[i], B[i]))

输出位数最多的一行是 586061125622639 144403552893600。由此发现边算边约分，并不会爆 long long。于是这题就可以直接用 c++ A掉了。具体恶心的输出格式详见代码。

---

变量解释与参考代码 (c++11):

A[i] 为调和级数前缀和第 i 项的分子

B[i] 为调和级数前缀和第 i 项的分母

void Red(ll &m, ll &n) 对 &m 和 &n 进行约分

int Len(ll n) 返回整数 n 的数位个数

#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

int N;
ll A[35] = {0, 1}, B[35] = {0, 1};
// B[1] 需要预处理，否则无法计算

inline void Red(ll &m, ll &n) {
  ll d = __gcd(m, n);
    // 库函数 __gcd() 联赛不可用
  m /= d, n /= d;
}

inline void init() {
  for(ll i = 2, a, b; i <= 33; ++i) {
    a = A[i - 1], b  = B[i - 1];
    A[i] = (ll)a * i + b;
    B[i] = (ll)b * i;
    Red(A[i], B[i]);
  }
}

inline int Len(ll n) {
  int ans = 0;
  do ++ans; while(n /= 10);
    // do-while 可以避免 n == 0 的情况出错
    // 不过在这里用 while 也不会出问题
  return ans;
}

int main() {
  init();
  while(cin >> N) {
    ll a = A[N] * N, b = B[N];
    Red(a, b); // 由于乘了一个 $N，需要再次约分
    if(b == 1) {
      // 如果能整除，直接特判，不需输出分数
      cout << a << '\n';
      continue;
    }
    ll k = a / b; // k 为带分数的整数部分
    a -= k * b;
    int lb = Len(b), lk = Len(k);
    
    // 以下分别输出带分数的三行
    for(int i = 1; i <= lk + 1; ++i)
      cout << ' ';
    cout << a << '\n';
    
    cout << k << ' ';
    for(int i = 1; i <= lb; ++i)
      cout << '-';
    cout << '\n';
    
    for(int i = 1; i <= lk + 1; ++i)
      cout << ' ';
    cout << b << '\n';
  }
  return 0;
}

如果有错误或不懂的地方，请在私信或评论中告知我。谢谢大家qwq