Tower

题意概述

有一个数列，$a_1=1, \ a_n=2a_2a_{n-1}-a_{n-2}$。给定$a_2$，求这个数列前$N$项的平方和模$M$。有$T$组数据。

数据范围：$1 \le T \le 10^5, \ 1 \le a_2, M \le 10^9, \ 2 \le N \le 10^9$。

算法分析

设$p=2a_2$，$S_n$表示前$n$项的平方和（不包括前两项）。

那么

$$
\begin{align}
& a_n^2=(pa_{n-1}-a_{n-2})^2=p^2a_{n-1}^2-2pa_{n-1}a_{n-2}+a_{n-2}^2 \\
& S_n=S_{n-1}+a_n^2 \\
& a_na_{n-1}=a_{n-1}(pa_{n-1}-a_{n-2})=pa_{n-1}^2-a_{n-1}a_{n-2}
\end{align}
$$

这几个递推式可以用矩阵乘法来表示

$$
\begin{bmatrix}
p^2 & 1 & -2p & 0 \\
1 & 0 & 0 & 0 \\
p & 0 & -1 & 0 \\
1 & 0 & 0 & 1
\end{bmatrix} \times
\begin{bmatrix}
a_n^2 \\
a_{n-1}^2 \\
a_na_{n-1} \\
S_{n-1}
\end{bmatrix}=
\begin{bmatrix}
a_{n+1}^2 \\
a_n^2 \\
a_{n+1}a_n \\
S_n
\end{bmatrix}
$$

用快速幂来加速递推，可以在$O(\log N)$的时间复杂度内完成。