[知识点] 万能欧几里得

例题

LOJ6440

做法

考虑这样一个问题:作一条射线 \(y = \frac{Px+R}Q\),只考虑 \(x > 0\),碰到一条直线 \(y = i\) 就执行操作 \(A\),碰到一条直线 \(x = i\) 就执行操作 \(B\)\(i\) 是正整数。

“操作序列”对应的信息要可合并。

考虑递归地处理问题,设 \(A\)\(B\) 是两个操作序列对应的信息。定义 \(solve(P, Q, R, L, A, B)\) 表示一个含有 \(L\)\(B\),第 \(k\)\(B\) 和第 \(k-1\)\(B\) 之间有 \(\lfloor \frac{Pk+R}Q \rfloor - \lfloor \frac{P(k-1)+R}Q \rfloor\)\(A\) 的操作序列的信息(\(k = 1\) 时是开头 \(A\) 的数量)。把 \(R\)\(Q\) 取模不会改变答案,把 \(P\)\(Q\) 取模只要把 \(B\) 变成 \(A^{\lfloor \frac P Q \rfloor}B\) 就可以得到同样的结果。

先取模,保证 \(P, R < Q\)

考虑交换 \(A\)\(B\) 的地位,原来我们是考虑每个 \(B\) 前面有几个 \(A\),现在我们考虑每个 \(A\) 前面有几个 \(B\),第 \(i\)\(A\) 在第 \(j\)\(B\) 前面的条件是 \(i \le \frac{Pj+R}{Q}\),即 \(j \ge \frac{Qi-R}P\)。那么第 \(i\)\(A\) 在第 \(j\)\(B\) 后面的条件是 \(j < \frac{Qi-R}P\),从第 \(i\)\(A\) 前面有 \(\max(0, \lceil \frac {Qi-R}P \rceil-1) = \max(0, \lfloor \frac{Qi-R-1}{P}\rfloor)\)\(B\)。我们只需要特别去处理一下最后一个 \(A\) 后面的 \(B\)\(Qi-R-1\) 小于 \(0\) 的情况即可得到一个形式一样的问题。由于 \(R < Q\)\(i > 0\)\(Qi-R-1 \ge 0\)。但是 \(i = 0\) 时出现负数按之前的定义会出问题,所以第一个 \(A\) 以及前面的部分单独处理,调用 \(solve(Q, P, Q-R-1, \lfloor \frac{PL+R}{Q} \rfloor - 1, B, A)\),处理下开头结尾即可。要判一下没有 \(A\) 的情况。

涉及到求矩阵幂可以直接快速幂,可以证明复杂度仍是一个 \(\log\)