---
title: Tower
tags:
  - Exponentiation by Squaring
id: "173"
categories:
  - - OI
    - Common Skill
date: 2017-06-06 21:30:18
---

## 题意概述

有一个数列，$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)$的时间复杂度内完成。