几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

标签 矩阵乘法 下的文章

官方题解是什么神仙东西看啊看不懂的。

Link

考虑我们维护一个分数类 (x, y) 表示 \frac x y 。假设 f(a_1, a_2, ..., a_n) = \frac x y 那么 f(a_0, a_1, a_2, ..., a_n) = \frac {a_0 x + y} {x} 。可以考虑用矩阵来维护转移。

定义将 (x, y)(a x + y, x) 的转移为

\left[\begin{matrix} a & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} x \\ y \\ \end{matrix}\right] = \left[\begin{matrix} ax + y \\ x \end{matrix}\right]

反之,从 (ax + y, x)(x, y) 的转移为

\left[\begin{matrix} 0 & 1 \\ 1 & -a \\ \end{matrix}\right] \left[\begin{matrix} ax + y \\ x \\ \end{matrix}\right] = \left[\begin{matrix} x \\ y \\ \end{matrix}\right]

那么

\begin{aligned} Ans_{l, r} &= \left[\begin{matrix} a_l & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_{l + 1} & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \\ &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 1} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{l - 2} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_r & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \end{aligned}

可以分别处理出前缀和

\begin{aligned} F_n &= \left[\begin{matrix} a_1 & 1 \\ 1 & 0 \\ \end{matrix}\right] \left[\begin{matrix} a_2 & 1 \\ 1 & 0 \\ \end{matrix}\right] \cdots \left[\begin{matrix} a_n & 1 \\ 1 & 0 \\ \end{matrix}\right] \\ G_n &= \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n} \\ \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & -a_{n - 1} \\ \end{matrix}\right] \cdots \left[\begin{matrix} 0 & 1 \\ 1 & -a_1 \\ \end{matrix}\right] \end{aligned}

READ MORE