P8348 「Wdoi-6」未知之花魅知之旅

题意

设一个好的序列由 \(a_0\) 与 \(a_1\) 生成而来。

满足，对于 \(1 < i < n\)，\(a_{i - 1}, a_i, a_{i + 1}\) 中最大一个数等于其他两个之和，以及所以元素都不小于 \(k\)。

有 \(T\) 次询问，每次给定 \((a_0, a_1, x, y, k)\) 满足限制，且有序列 \(a\) 中有两项相邻依次为 \(x, y\)。

\(n \le 10 ^ 9\)

Sol

不难发现，因为操作显然可逆，我们可以找到中间点 \((c, d)\) 使得从 \((a_0, a_1)\) 操作至 \((c, d)\) 且 \((y, x)\) 操作至 \((d, c)\)。

考虑用一些方式映射一个序列，使得存在这样的 \((c, d)\) 可以用来表示整个序列。

显然注意到 \(k\) 的限制，因此考虑下界。手玩一下可以发现，事实上加法是没有用的，因为一次加法后进行两次减法后序列最后两位不变：

\(a, b \to a, b, a + b \to a, b, a + b, a \to a, b, a + b, a, b\)

然后我们又可以显然发现若序列中只存在一次加法后面只有一次减法的操作，该序列的最后两位是不会减小的。

因此可以证明，得到 \((c, d)\) 的映射只能通过减法操作。

补充 \((c, d)\) 的定义为 只进行一次 减法操作就能打破 \(k\) 的限制。

由于减法操作是唯一确定的，所以映射也是唯一确定的。

直接模拟减法是无法通过的，复杂度为 \(O(n)\)。

注意到该操作是辗转相减状物，直接用欧几里得算法优化即可。