对于一条直线 $\frac {a x + b} c$ ，如果穿过整数直线，与 $x$ 平行则执行 $U$ ，与 $y$ 平行则执行 $R$ 。那么可以在 $\log(a + c)$ 时间内完成 $n$ 内的操作。
例题 I
求 $\sum\limits_{i=0}^{n}\lfloor \frac{ai+b}{c} \rfloor, \sum\limits_{i=0}^{n}{\lfloor \frac{ai+b}{c} \rfloor}^2, \sum\limits_{i=0}^{n}i\lfloor \frac{ai+b}{c} \rfloor$ 。
对于第一个问题，对于 $U$ 操作为 ++t ，对于 $R$ 操作为 res += t 。那么可以刻画出这个问题。
考虑结合，两组操作如何合并。记 $f, g, h$ 为三个问题的答案，$u, r$ 表示两种操作的操作的次数。考虑操作 $1$ 对操作 $2$ 的增加的贡献，记 $s _ i$ 表示在 $i$ 处的点值，那么有
$$
\begin {aligned}
f & = \sum _ {i = 0} ^ {r - 1} s _ i \\
g & = \sum _ {i = 0} ^ {r - 1} s _ i ^ 2 \\
h & = \sum _ {i = 0} ^ {r - 1} i s _ i
\end {aligned}
$$
$$
\begin {aligned}
f & \gets f _ 1 + \sum _ {i = 0} ^ {r _ 2 - 1} (s _ i + u _ 1) = f _ 1 + f _ 2 + u _ 1 r _ 2 \\
g & \gets g _ 1 + \sum _ {i = 0} ^ {r _ 2 - 1} (s _ i + u _ 1) ^ 2 = g _ 1 + \sum _ {i = 0} ^ {r _ 2 - 1} (s _ i ^ 2 + 2s _ i u _ 1 + u _ 1 ^ 2) = g _ 1 + g _ 2 + 2 f _ 2 u _ 1 + u _ 1 ^ 2 r _ 2 \\
h & \gets h _ 1 + \sum _ {i = 0} ^ {r _ 2 - 1} (i + r _ 1) (s _ i + u _ 1) = h _ 1 + h _ 2 + \frac {r _ 2 (r _ 2 - 1)} 2u _ 1 + r _ 1 f _ 2 + r _ 2 r _ 1 u _ 1
\end {aligned}
$$
另外注意对于开头的处理。
查看代码
1 |
|
例题II
求 $\sum\limits_{x=1}^LA^xB^{\left\lfloor\frac{Px+R}{Q}\right\rfloor}$ 。其中 $A, B$ 为矩阵。
此题中，$U$ 操作为在后面乘 $B$ ，$R$ 操作为在前面乘 $A$ ，并将答案贡献上。那么两组操作合并，考虑第一组对第二组的影响，即将 $A ^ {k _ A}$ 乘在前面，$B ^ {k _ B}$ 乘在后面。
查看代码
1 |
|