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)$的时间复杂度内完成。

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *