大约是翻译了一下官方题解?
@Description@
对于一个整数序列 $P=(P_{1},\dots,P_{m})$,定义 $f(P)$ 为一个序列 $Q$ 满足:
- $Q_{i}=P_{i}+P_{i+1}$,其中 $i\in[1,m)$;
- $f(P)=(P_{1},Q_{1},\dots,P_{m-1},Q_{m-1},P_{m})$。
给出正整数 $a,b,N$,其中 $a,b\leqslant N$,令序列 $A=(a,b)$,令序列 $B$ 为一下操作的结果:
- 做 $N$ 次令 $A=f(A)$.
- 删除 $A$ 中大于 $B$ 的数。
求 $B_{l,\dots r}$。
@Solution@
◆ The Coefficient Sequence
构造最终的 $A$ 序列的过程是这样的:
$$ a,b \\ a,a+b,b \\ a,2a+b,a+b,a+2b,b \\ a,3a+b,2a+b,3a+2b,a+b,2a+3b,a+2b,a+3b,b \\ \dots $$
可以发现有对称性。此时我们先不关心 $a,b$ 以及 $N$ 的大小,反之,我们来观察其序列系数,也就是把每个元素看成 $xa+yb$,其系数的 $(x,y)$,上例的序列系数即
$$ (1,0),(0,1) \\ (1,0),(1,1),(0,1) \\ (1,0),(2,1),(1,1),(1,2),(0,1) \\ (1,0),(3,1),(2,1),(3,2),(1,1),(2,3),(1,2),(1,3),(0,1) \\ \dots $$
以下我们称其为 Coefficient Sequence。
◆ The properties of the Coefficient Sequence
现在我们来观察 Coefficient Sequence 的性质。
Observation 1:在 Coefficient Sequence 中相邻的两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$,都有: $x_{S}y_{T}-x_{T}y_{S}=1$。
使用数学归纳法(induction)即证。
Observation 2:对于两个 两个二元组 $(x_{S},y_{S}),(x_{T},y_{T})$,如果他们满足 $x_{S}y_{T}-x_{T}y_{S}=1$,那么它们在 Coefficient Sequence 中相邻,即 Observation 1 是充要条件。
不会证,大概意会一下吧。
Observation 3:对于一个二元组 $(x,y)$,如果 $\gcd(x,y)=1$,那么 $(x,y)$ 会出现在 Coefficient Sequence 中。
比较显然,以至于官方题解没有给出证明。
Observation 4:在任意时刻,所有在 Coefficient Sequence 中的 $(x,y)$ 总是呈从左到右的关于值 $\frac{y}{x}$ 递增(令 $\frac{x}{0}=\infty$)。
◆ The sequence $B$ in other words
现在描述序列 $B$ 变得更加容易,现在我们这样描述它:
对于所有二元组 $(x,y)$ 满足 $x,y,s.t.x,y\in\mathbb{N},\gcd(x,y)=1,ax+by\leqslant N$,我们对其按 $\frac{y}{x}$ 排序后形成一个二元组序列 $\{(x_{i},y_{i})\}$,则 $B_{i}=ax_{i}+by_{i}$。
◆ Computing $B_{n}$
现在我们来考虑原问题的简化版,我们来计算 $B_{n}$。让我们把这个描述成一个计数问题(通过二分 $\frac{y}{x}$):
给定正整数 $a,b,N$,以及一个有理数 $c$(二分的值),求二元组 $(x,y)\neq(0,0)$ 的数量,其中 $(x,y)$ 满足
- $ax+by\leqslant N$;
- $\gcd(x,y)=1$;
- $\frac{y}{x}\leqslant c$。
我们令 $F(N)$ 为以上问题的答案,同时令 $G(N)$ 为去掉 $\gcd(x,y)=1$ 限制的答案。$G(N)$ 的式子可以很方便的写出来: $G(N)=\sum_{y=1}^{N}\max\{\lfloor\frac{N-by}{a}\rfloor-\lfloor\frac{y}{c}\rfloor+1,0\}$,同时我们还可以写出 $G(N)=\sum_{d=1}^{N}F(\lfloor\frac{N}{d}\rfloor)$。那么再根据 Möbius inversion formula,我们可以表示出 $F(N)=\sum_{d=1}^{N}\mu(d)G(\lfloor\frac{N}{d}\rfloor)$。于是计算该问题答案的复杂度就是 $\mathcal{O}(N)$。
但是此时我们知道了 $B_{n}$ 的 $\frac{y_{n}}{x_{n}}$,怎么知道 $(x_{n},y_{n})$ 呢?我们可以再做一个二分。观察出这样一个规律:若令 $l=(1,0),r=(0,1)$,那么中间位置就是 $l+r$。于是我们可以再次做一个二分,利用 $\frac{y}{x}$ 单调来做 check。
顺带一提,这个还可以使用 类欧几里得 来计算。
◆ Computing $B_{l,\dots,r}$
可以发现这个东西可以知二求一,于是求出 $B_{l},B_{l+1}$ 就行了。当然也可以求出 $B_{l},B_{r}$ 然后做二分搜索。