题解 P5175 【数列】

Kevin_Zhen · 2021-04-28 19:47:44 · 题解

题目链接 \mathfrak{P5175}。
萌新的第一篇矩阵加速相关题解，求资瓷！qwq

题目大意

一个数列 a_n，已知 a_1、a_2 两项及两个系数 x 和 y，数列 a_n 满足递推式 a_i=x\times a_{i-1}+y\times a_{i-2}\ (i\ge 3)，求 \sum_{i=1}^{n}{{a_i}^2}\ (n\le 10^{18})。

解题思路

题目相比于普通的矩阵加速，最大的难点在于所求答案为各项平方和。我们需要通过 S_{i-1} 和 {a_i}^2 求解 S_i\ (S_i=\sum_{j=1}^i{{a_j}^2})，即 S_i=S_{i-1}+{{a_i}^2}。根据构造矩阵时，要将求解所求答案所需元素放入构造矩阵中的思路，我们不妨直接将 {a_i}^2 放入构造矩阵中，在接下来的做题过程中也应更多关注于 {a_i}^2 的求解，而非 a_i（a_i 并未用到）。

先确定矩阵转移方程。假设我们当前要由矩阵 (i-1) 转移到矩阵 i 吧。
首先要包括所求内容，当前两矩阵分别为：\begin{bmatrix}S_i\end{bmatrix} 和 \begin{bmatrix}S_{i-1}\end{bmatrix}。
求解 S_i 需要用到 {a_i}^2，所以矩阵 (i-1) 变为 \begin{bmatrix}S_{i-1}\\{a_i}^2\end{bmatrix}，相应地，矩阵 i 变为 \begin{bmatrix}S_i\\{a_{i+1}}^2\end{bmatrix}。
由 a_{i+1}=x\times a_i+y\times a_{i-1} 得，矩阵 i 变为 \begin{bmatrix}S_i\\(xa_i+ya_{i-1})^2\end{bmatrix}。此时两矩阵分别为：\begin{bmatrix}S_i\\x^2{a_i}^2+y^2{a_{i-1}}^2+2xya_ia_{i-1}\end{bmatrix} 和 \begin{bmatrix}S_{i-1}\\{a_i}^2\end{bmatrix}。
从矩阵 i 中可以看出，要想求得矩阵 i，矩阵 (i-1) 中还需放入 {a_{i-1}}^2 和 a_ia_{i-1} 两项。将这两项放入矩阵 (i-1)，两矩阵相应变为：\begin{bmatrix}S_i\\x^2{a_i}^2+y^2{a_{i-1}}^2+2xya_ia_{i-1}\\{a_i}^2\\a_{i+1}a_i\end{bmatrix} 和 \begin{bmatrix}S_{i-1}\\{a_i}^2\\{a_{i-1}}^2\\a_ia_{i-1}\end{bmatrix}。
最后再次用 a_{i+1}=x\times a_i+y\times a_{i-1} 消去矩阵 i 中的 a_{i+1}，得到最终的两矩阵：