P1797 【模板】Stern-Brocot 树
洛谷同步题解。
前置知识：\(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 序列。
例如：
- \(1\) 阶是 \(\{ \frac{0}{1}, \frac{1}{1}, \frac{1}{0} \}\)。
- \(2\) 阶是 \(\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0} \}\)。
- \(3\) 阶是 \(\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0} \}\)。
容易看作二叉树的结构：
- 每个分数都是 \(\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_);
- }
- 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 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
