tower.md 1.1 KB
title: Tower tags:
- Exponentiation by Squaring id: "173" categories:
- - OI
- Common Skill date: 2017-06-06 21:30:18 ---
题意概述
有一个数列，$a_1=1, \; a_n=2a2a{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} & an^2=(pa{n-1}-a{n-2})^2=p^2a{n-1}^2-2pa{n-1}a{n-2}+a_{n-2}^2 \\ & Sn=S{n-1}+a_n^2 \\ & ana{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} an^2 \\ a{n-1}^2 \\ ana{n-1} \\ S{n-1} \end{bmatrix}= \begin{bmatrix} a{n+1}^2 \\ an^2 \\ a{n+1}a_n \\ S_n \end{bmatrix} $$
用快速幂来加速递推，可以在$O(\log N)$的时间复杂度内完成。