UVA11350 Stern-Brocot Tree

Genius_Star · 2026-01-24 12:55:40 · 题解

或许更好的阅读体验。

思路：

前置知识：a \perp b 等价于存在 x, y 使得 ax + by = 1。

Stern-Brocot 树是一个包含着所有 m \perp n 的全部非负的分数 \frac{m}{n} 的二叉树结构；其思想是从 0 阶 Stern-Brocot 序列 \{\frac{0}{1}, \frac{1}{0} \} 出发，高阶 Stern-Brocot 序列由以下递归操作定义：

对于一个 k 阶 Stern-Brocot 序列，在其任意两个相邻分数 \frac{m}{n} 与 \frac{m'}{n'} 之间插入它们的中位分数 \frac{m + m'}{n + n'} 后形成的序列即为 k + 1 阶 Stern-Brocot 序列。

例如：

容易看作二叉树的结构：

每个分数都是 \frac{m + m'}{n + n'} 的形式，其中 \frac{m}{n} 是左上方离它最近的祖先，\frac{m'}{n'} 是右上方离它最近的祖先。

oi-wiki 上的图较为形象，大家可以看着理解下：

为什么树上的都是最简分数？为什么不会重复出现某个分数？为什么所有可能的非负的最简分数都会在树上出现？

容易发现这样一个性质，如果 \frac{m}{n} 和 \frac{m'}{n'} 在某一阶的 Stern-Brocot 序列中相邻，那么必然满足：

m'n - mn' = 1

证明考虑数学归纳法，初始 0 阶时有 1 \cdot 1 - 0 \cdot 0 = 1；若当前 k 阶 Stern-Brocot 序列中满足条件，那么在 \frac{m}{n} 与 \frac{m'}{n'} 中间插入的 \frac{m + m'}{n + n'}，相当于要证明：
(m' + m)n - m(n + n') = 1 m'(n + n') - (m + m') n' = 1
第一个直接拆开 m'n + mn - mn - mn' = m'n - mn' = 1，第二个同理；于是得证。

同时，上面 m'n - mn' = 1 这个式子也可以说明 m \perp n, m' \perp n'，那么可以得到树上的所有分数必然是最简分数。

然后来考虑插入的分数的大小关系，显然有：

\frac{m}{n} < \frac{m + m'}{n + n'} < \frac{m'}{n}

即一个中位分数在它原先两个值的中间，于是树上必然没有重复的分数。

好，接下来要证所有正的最简分数 \frac{a}{b} 都在树上出现，考虑反证法，初始显然：

\frac{m = 0}{n = 1} < \frac{a}{b} < \frac{m' = 1}{n' = 0}

然后假设当前阶段有：

\frac{m}{n} < \frac{a}{b} < \frac{m'}{n'}

考虑 \frac{m + m'}{n + n'} 与 \frac{a}{b} 的大小关系：

若 \frac{m + m'}{n + n'} = \frac{a}{b}，与命题矛盾，退出。
若 \frac{m + m'}{n + n'} < \frac{a}{b}，令 m \gets m + m', n' + n。
否则 \frac{m + m'}{n + n'} > \frac{a}{b}，令 m' \gets m + m', n' \gets n + n'。

考虑证明这个过程不会无限进行下去，因为：

\begin{cases} \frac{a}{b} - \frac{m}{n} > 0 \\ \frac{m'}{n'} - \frac{a}{b} > 0 \end{cases}

即：

\begin{cases} an - mb > 0 \\ m'b - n'a > 0 \end{cases}

显然 an - mb, m'b - n'a 都是整数，于是：

\begin{cases} an - mb \ge 1 \\ m'b - n'a \ge 1 \end{cases}

然后必然有：

(m' + n')(an - mb) + (m + n)(m'b - n'a) \ge m' + n' + m + n

前面把 a 和 b 专门提出来：

a(n(m' + n') - n'(m + n)) + b(m'(m + n) - m(m' + n'))

然后它们的系数可以根据 m'n - mn' = 1 化简成 1，于是：

a + b \ge m' + n' + m + n

而上面每次操作中 m' + n' + m + n 都会增加，于是至多进行 a + b 次后就会退出，即找到 \frac{a}{b}；于是证明了所有非负分数即正有理数都在树上，可以将 Stern-Brocot 树看作一个有理数的数系。

因为每个正最简分数只出现一次，所以其与树上从根到它的路径是一一对应的，即我们可以用字母 L, R 来表示当前节点是往左右哪个儿子去走，一串 L, R 组成的序列就唯一的表示了一个位置；例如 LRRL 表示 \frac{1}{1} \to \frac{1}{2} \to \frac{2}{3} \to \frac{3}{4} \to \frac{5}{7}；特别的，对于 \frac{1}{1} 用 I 来表示。

考虑这样一个问题，给出一组 L, R 组成的字符串 S，求出其对应的分数是什么？

容易想到从初始 \frac{1}{1} 开始，动态维护这个点是由左右哪两个节点合并的，初始是 \frac{m = 0}{n = 1}, \frac{m' = 1}{n' = 0}：

若 L 往左走：那么左祖先不会变，右祖先会变成当前节点；即 m' \gets m + m', n' \gets n + n'。
若 R 往右左：同理，那么右祖先不会变，左祖先会变成当前节点；即 m \gets m + m', n \gets n + n'。

大家理解的时候可以看前面那个树的图来理解；然后我们就可以写下如下代码解决：

inline pair<int, int> getLR(string s){
    int len = s.size();
    int m = 0, n = 1, m_ = 1, n_ = 0;
    for(int i = 0; i < len; ++i){
        if(s[i] == 'L')
          m_ = m + m_, n_ = n + n_;
        else
          m = m + m_, n = n + n_;
    }
    return mkp(m + m_, n + n_);
}

当长度很长时，即给定是 L/R 每次走几次，也可以根据式子直接做：

inline pair<int, int> getLR(vector<pair<char, int>> s){
    int len = s.size();
    int m = 0, n = 1, m_ = 1, n_ = 0;
    for(int i = 0; i < len; ++i){
        if(s[i].fi == 'L')
            m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
        else
            m = m + s[i].se * m_, n = n + s[i].se * n_;
    }
    return mkp(m + m_, n + n_);
}

这种还是太程序性了，数学语言怎么表示？容易想到矩阵，即初始：

M(S) = \begin{pmatrix} n & n' \\ m & m' \end{pmatrix}

这里为啥不用像分数那样上面分子下面分母呢？主要是此时初始根节点的状态 M(I) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} 这是一个单位矩阵，而用分数的表示形式的话不是单位矩阵要多乘一个矩阵，形式上也不那么清晰。

然后考虑：

M(SL) = \begin{pmatrix} n & n + n' \\ m & m + m' \end{pmatrix}

M(SR) = \begin{pmatrix} n + n' & n' \\ m + m' & m' \end{pmatrix}

那么可以推出 L, R 矩阵：

L = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}

R = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}

即：

M(SL) = M(S) L, M(SR) = M(S) R

于是求 M(S) 时，可以看作是 S 中的 L, R 作矩阵乘法，例如 M(LRRL) = LRRL = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 3 & 4 \\ 2 & 3 \end{pmatrix}。

于是求 S 所对应的分数只需要经过矩阵运算得到：

f(S) = f(\begin{pmatrix} n & n' \\ m & m' \end{pmatrix}) = \frac{m + m'}{n + n'}

那么现在考虑给定一个分数 \frac{m}{n}，求其唯一对应 LR 序列这个问题？这就比较简单了，根据生成规则，我们知道 Stern-Brocot 树是一颗二叉搜索树，即左子树的点都比它小，右子树的点都比它大，于是可以通过比较与当前位置的值来决定。

那么可以写下如下代码：

inline string backLR(int m, int n){
    string ans = "";
    Mat S;
    while(1){
        auto t = f(S);
        if(t == mkp(m, n))
          break;
        if(mkp(m, n) < t){
            S = S * L;
            ans.push_back('L');
        }
        else{
            S = S * R;
            ans.push_back('R');
        }
    }
    return ans;
}

显然，这个效率较为低下，且要进行矩阵运算；考虑怎么优化一下，注意到：

RS = \begin{pmatrix} n & n' \\ m + n & m' + n'\end{pmatrix}

LS = \begin{pmatrix} n + m& n' + m' \\ m& m'\end{pmatrix}

那么：

f(RS) = \frac{n + n'}{m + n + m' + n'} = f(S) + 1

f(LS) = \frac{n + m + n' + m'}{m + m'}

\frac{1}{f(LS)} = \frac{1}{f(LS)} + 1

设 F(\frac{p}{q}) 表示其对应的字符串；那么我们可以看出，若第一步为 R，则 \frac{m}{n} > 1，否则第一步为 L，则 \frac{m}{n} < 1，于是可以递归的去做：

\frac{m}{n} = f(RS) \to \frac{m - n}{n} = f(S) (m > n)

F(\frac{m}{n}) = R + F(\frac{n}{m - n}) (m > n)

\frac{m}{n} = f(LS) \to \frac{m}{n - m} = f(S) (m < n)

F(\frac{m}{n}) = L + F(\frac{m}{n - m}) (m <n)

那么可以写出如下代码：

inline string backLR(int m, int n){
    string ans = "";
    while(m != n){
        if(m < n){
            ans.push_back('L');
            n = n - m;
        }
        else{
            ans.push_back('R');
            m = m - n;
        }
    }
    return ans;
}

你发现这特别像更像减损法，于是可以用辗转相除法类似的思路去优化，即：

inline vector<pair<char, int>> backLR(int m, int n){
    vector<pair<char, int>> ans;
    while(m && n && m != n){
        if(m < n){
            if(n % m == 0)
              ans.push_back({'L', n / m - 1});
            else
              ans.push_back({'L', n / m});
            n = n % m;
        }
        else{
            if(m % n == 0)
              ans.push_back({'R', m / n - 1});
            else
              ans.push_back({'R', m / n});
            m = m % n;
        }
    }
    return ans;
}

此时就可以做到 O(\log n) 复杂度去找对应的路径。

然后对于一个分数 \frac{p}{q}，考虑其在树上一个子树 S，显然 S 是无限大的，但是显然其有界，在 (\frac{a}{b}, \frac{c}{d}) 之间，那么怎么求出 a, b, c, d 呢？回到前面每次插入的中位分数在两个值之间的性质，于是这只是换一个问法，显然只是在问合并出 \frac{p = a + c}{q = b + d} 的是哪两个分数，比较简单，求出 \frac{p}{q} 的 LR 串后模拟一下即可。

对于树上问题，容易想到 LCA，那么考虑 Stern-Brocot 树上的两个点 \frac{a}{b}, \frac{c}{d}，怎么求出它们的 LCA？容易发现，找到 \frac{a}{b}, \frac{c}{d} 的 LR 串 F(\frac{a}{c}), F(\frac{c}{d})，它们 LCP 的长度就是它们 LCA 的深度；而这个长度是容易求的，然后它们的 LCA 就是这个 LCP 对应的节点，套用上面函数一下即可。

同理，\frac{p}{q} 的树上 k 级祖先也是可以算出 F(\frac{p}{q}) 后删掉末尾的 k 个字符后套用前面函数得出。

显然单次时间复杂度都是 O(len)，总时间复杂度为 O(\sum len)。

link

完整代码：

#include<bits/stdc++.h>
#define int long long
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline pair<int, int> getLR(vector<pair<char, int>> s){
    int len = s.size();
    int m = 0, n = 1, m_ = 1, n_ = 0;
    for(int i = 0; i < len; ++i){
        if(s[i].fi == 'L')
            m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
        else
            m = m + s[i].se * m_, n = n + s[i].se * n_;
    }
    return mkp(m + m_, n + n_);
}
inline vector<pair<char, int>> backLR(int m, int n){
    vector<pair<char, int>> ans;
    while(m && n && m != n){
        if(m < n){
            if(n % m == 0)
                ans.push_back({'L', n / m - 1});
            else
                ans.push_back({'L', n / m});
            n = n % m;
        }
        else{
            if(m % n == 0)
                ans.push_back({'R', m / n - 1});
            else
                ans.push_back({'R', m / n});
            m = m % n;
        }
    }
    return ans;
}
inline pair<int, int> getkfa(int m, int n, int k){
    auto V = backLR(m, n);
    int sum = 0, len = V.size();
    for(int i = 0; i < len; ++i)
        sum += V[i].se;
    if(sum < k)
        return mkp(-1, -1);
    vector<pair<char, int>> fa;
    for(int i = 0; i < len; ++i){
        if(!k)
            break;
        if(V[i].se <= k){
            fa.push_back(V[i]);
            k -= V[i].se;
        }
        else{
            fa.push_back(mkp(V[i].fi, k));
            k = 0;
        }
    }
    return getLR(fa);
}
inline pair<pair<int, int>, pair<int, int>> range(int p, int q){
    auto s = backLR(p, q);
    int len = s.size();
    int m = 0, n = 1, m_ = 1, n_ = 0;
    for(int i = 0; i < len; ++i){
        if(s[i].fi == 'L')
            m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
        else
            m = m + s[i].se * m_, n = n + s[i].se * n_;
    }
    return mkp(mkp(m, n), mkp(m_, n_));
}
inline pair<int, int> getlca(int a, int b, int c, int d){
    auto A = backLR(a, b), B = backLR(c, d);
    int s1 = 0, s2 = 0;
    for(auto v : A)
        s1 += v.se;
    for(auto v : B)
        s2 += v.se;
    if(s1 < s2){
        swap(a, c), swap(b, d);
        swap(A, B);
    }
    vector<pair<char, int>> lca;
    int j = 0;
    for(int i = 0; i < (int)A.size(); ++i){
        int s = A[i].se;
        while(j < (int)B.size() && s){
            if(B[j].fi != A[i].fi)
                break;
            if(B[j].se <= s){
                s -= B[j].se;
                ++j;
            }
            else{
                B[j].se -= s;
                s = 0;
            }
        }
        if(j == (int)B.size() || s){
            lca.push_back(mkp(A[i].fi, A[i].se - s));
            break;
        }
        lca.push_back(A[i]);
    }
    return getLR(lca);
}
int T;
string s;
signed main(){
    T = read();
    while(T--){
        vector<pair<char, int>> V;
        cin >> s;
        for(auto c : s)
          V.push_back(mkp(c, 1));
        auto t = getLR(V);
        write(t.fi);
        putchar('/');
        write(t.se);
        putchar('\n');
    }
    return 0;
}