Solution -「ARC 123F」Insert Addition

大约是翻译了一下官方题解？

@Description@

对于一个整数序列 (P=(P_{1},dots,P_{m}))，定义 (f(P)) 为一个序列 (Q) 满足：

(Q_{i}=P_{i}+P_{i+1})，其中 (iin[1,m))；
(f(P)=(P_{1},Q_{1},dots,P_{m-1},Q_{m-1},P_{m}))。

给出正整数 (a,b,N)，其中 (a,bleqslant 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)）。

(B) in other words

现在描述序列 (B) 变得更加容易，现在我们这样描述它：

对于所有二元组 ((x,y)) 满足 (x,y,s.t.x,yinmathbb{N},gcd(x,y)=1,ax+byleqslant N)，我们对其按 (frac{y}{x}) 排序后形成一个二元组序列 ({(x_{i},y_{i})})，则 (B_{i}=ax_{i}+by_{i})。

(B_{n})

现在我们来考虑原问题的简化版，我们来计算 (B_{n})。让我们把这个描述成一个计数问题（通过二分 (frac{y}{x})）：

给定正整数 (a,b,N)，以及一个有理数 (c)（二分的值），求二元组 ((x,y) eq(0,0)) 的数量，其中 ((x,y)) 满足

(ax+byleqslant 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{lfloorfrac{N-by}{a} floor-lfloorfrac{y}{c} floor+1,0})，同时我们还可以写出 (G(N)=sum_{d=1}^{N}F(lfloorfrac{N}{d} floor))。那么再根据 Möbius inversion formula，我们可以表示出 (F(N)=sum_{d=1}^{N}mu(d)G(lfloorfrac{N}{d} floor))。于是计算该问题答案的复杂度就是 (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。

顺带一提，这个还可以使用 类欧几里得 来计算。

(B_{l,dots,r})

可以发现这个东西可以知二求一，于是求出 (B_{l},B_{l+1}) 就行了。当然也可以求出 (B_{l},B_{r}) 然后做二分搜索。