普及一下线性代数科技。

认为本题中数据组数 $T\le 10^6$，项数 $n\le 10^{18}$。

矩阵

如下定义一个 $n$ 行 $m$ 列的矩阵 $A$：

$$\begin{bmatrix}A_{1,1}&\dots&A_{1,m}\\\vdots&\ddots&\vdots\\A_{n,1}&\dots&A_{n,m}\end{bmatrix} $$

$n,m$ 分别为矩阵的行数和列数。矩阵 $A$ 第 $i$ 行第 $j$ 列的元素被记作 $A_{i,j}$。

称两个矩阵相等，当且仅当她们行数和列数相同，且每个位置上的元素相同。

矩阵乘法

定义

$n$ 行 $m$ 列的矩阵 $A$ 和 $p$ 行 $q$ 列的矩阵 $B$ 能进行矩阵乘法运算，当且仅当 $m=p$。其结果为一个 $n$ 行 $q$ 列的矩阵 $C$，满足 $C_{i,j}=\sum\limits_{k=1}^mA_{i,k}B_{k,j}$。

结合律

由于本题的需要，文中只介绍行数和列数均为 $n$ 的情况。

$\bold {Lemma}$

对于三个 $n$ 行 $n$ 列的矩阵 $A,B,C$，有 $A\times B\times C=A\times (B\times C)$。

$\bold{Proof}$

等式左右的运算结果都是 $n$ 行 $n$ 列的矩阵，因此只需要证明两个矩阵中对应位置的元素相等。我们有：

$$(A\times B)_{i,j}=\sum\limits_{k=1}^nA_{i,k}B_{k,j} $$$$\begin{aligned}(A\times B\times C)_{i,j}&=\sum\limits_{k=1}^n(A\times B)_{i,k}C_{k,j}\\&=\sum\limits_{k_1=1}^nC_{k_1,j}\sum\limits_{k_2=1}^nA_{i,k_2}B_{k_2,k_1}\\&=\sum\limits_{k_1=1}^n\sum\limits_{k_2=1}^nA_{i,k_2}B_{k_2,k_1}C_{k_1,j}\end{aligned} $$$$(B\times C)_{i,j}=\sum\limits_{k=1}^nB_{i,k}C_{k,j} $$$$\begin{aligned}[A\times (B\times C)]_{i,j}&=\sum\limits_{k=1}^nA_{i,k}(B\times C)_{k,j}\\&=\sum\limits_{k_1=1}^nA_{i,k_1}\sum\limits_{k_2=1}^nB_{k_1,k_2}C_{k_2,j}\\&=\sum\limits_{k_1=1}^n\sum\limits_{k_2=1}^nA_{i,k_1}B_{k_1,k_2}C_{k_2,j}\end{aligned} $$

容易发现两个结果的和式之间的区别仅仅是交换求和顺序，因此 $(A\times B\times C)_{i,j}=[A\times (B\times C)]_{i,j}$。所以命题得证。

$\mathcal{Q.E.D.}$

分配律

矩阵乘法 一般不具有分配律。

回到本题

记斐波那契数列为 $f$。本题要求 $f_n$。记 $F_i=\begin{bmatrix}f_i&f_{i+1}\\0&0\end{bmatrix}$。根据斐波那契数列的定义 $f_i=f_{i-2}+f_{i-1}$ 可以得到：

$$F_i\times \begin{bmatrix}0 &1\\1&1\end{bmatrix}=F_{i+1}$$

那么 $F_n$ 可以通过 $F_0$ 乘以 $n$ 次 $\begin{bmatrix}0 &1\\1&1\end{bmatrix}$ 得到。根据矩阵乘法的结合律，我们有：

$$F_n=F_0\times \begin{bmatrix}0 &1\\1&1\end{bmatrix}^n$$

接下来记 $G=\begin{bmatrix}0 &1\\1&1\end{bmatrix}$。

快速幂

如果直接枚举一遍乘起来这篇题解就没有存在的必要了。记 $n$ 的二进制表示中为 $1$ 的位置依次为 $[a_1,\dots,a_k]$，则：

$$G^n=\prod\limits_{i=1}^kG^{2^{a_i}}$$

记 $g_i=G^{2^i}$。考虑 $g_i=g^2_{i-1}$，那么我们就可以 $\mathcal{O}(\log n)$ 次递推 $g_i$。接下来把所有 $g_{a_i}$ 乘起来即可得到 $G^n$。再用 $F_0$ 乘以 $G^n$ 即可得到目标矩阵。最后输出第一行第一列的元素即可。

时间复杂度 $\mathcal{O}(T\omega\log n)$。其中 $\omega$ 为矩阵乘法复杂度，本题中可以认为是 $\mathcal{O}(1)$。

光速幂

当 $T\le 10^7$，$n\le 10^{14}$ 时，能不能再给力一点？

能的兄弟，能的。我们考虑一个阈值 $B$，则 $n$ 可以表示成 $kB+r$，其中 $r\in[0,B)$。

令 $N$ 为 $n$ 的上界。

我们考虑 $G^n=\left(G^B\right)^k\times G^r$。预处理 $h_i=G^i,i\in [1,B]$，$H_i=h_B^i,i\in\left[1,\left\lfloor\dfrac{N}{B}\right\rfloor\right]$。那么 $G^n=H_k\times h_r$。这样单次查询只需要做一次矩阵乘法，时间复杂度为 $\mathcal{O}(\omega)$。

至于预处理，时间复杂度为 $\mathcal{O}\left( B+\dfrac{N}{B}\right)$。根据我们在数学必修一学过的均值不等式知识，可知当 $B=\mathcal{O}\left(\sqrt N\right)$ 时最优时间复杂度为 $\mathcal{O}\left(\sqrt N\right)$。

于是我们得到了一个时间复杂度为 $\mathcal{O}\left(\left(T+\sqrt N\right)\omega\right)$ 的做法。