自动搬运

查看原文

来自洛谷，原作者为

	Kevin_Zhen 不再回来

搬运于2025-08-24 22:07:55，当前版本为作者最后更新于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}$，得到最终的两矩阵：
$\begin{bmatrix}S_i\\x^2{a_i}^2+y^2{a_{i-1}}^2+2xya_ia_{i-1}\\{a_i}^2\\x{a_i}^2+ya_ia_{i-1}\end{bmatrix}$ 和 $\begin{bmatrix}S_{i-1}\\{a_i}^2\\{a_{i-1}}^2\\a_ia_{i-1}\end{bmatrix}$。
此时矩阵 $i$ 已经完全可以由矩阵 $(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\\x{a_i}^2+ya_ia_{i-1}\end{bmatrix}=\begin{bmatrix}1\ 1\ 0\ 0\\0\ x^2\ y^2\ 2xy\\0\ 1\ 0\ 0\\0\ x\ 0\ y\end{bmatrix}\times\begin{bmatrix}S_{i-1}\\{a_i}^2\\{a_{i-1}}^2\\a_ia_{i-1}\end{bmatrix}$。

时间复杂度为 $O(Tlogn\times m^3)$，其中 $m$ 为矩阵的边长。注意此题 $T\le 30000$，$log_210^{18}\approx 60$，时限为 $1.5s$，此时矩阵的边长已经不能当作一个常数忽略不计了。估算得 $m=4$ 时执行次数约为 $1.152\times 10^8$，边长大于 $4$ 的矩阵是无法接受的。

AC CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef unsigned long long ull;

const int Mod = 1e9 + 7;

struct Matrix {
	ull a[15][15]; int n, m;
	ull* operator [](int x) { return a[x]; }
	void clear() { n = 0, m = 0, memset(a, 0, sizeof(a)); }
};

Matrix operator *(Matrix &x, Matrix &y) {
	Matrix z; z.clear(); z.n = x.n, z.m = y.m;
	for (int i = 1; i <= x.n; ++i) {
		for (int j = 1; j <= x.m; ++j) {
			for (int k = 1; k <= y.m; ++k) z[i][k] = (z[i][k] + x[i][j] * y[j][k]) % Mod;
		}
	}
	return z;
}

int T;
ull n, a1, a2, x, y; Matrix a, b, ans;

Matrix qpow(Matrix base, ull p) {
	Matrix res = base; --p;
	while (p) {
		if (p & 1) res = res * base;
		base = base * base;
		p >>= 1;
	}
	return res;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		a.clear(); b.clear(); ans.clear();
		scanf("%llu%llu%llu%llu%llu", &n, &a1, &a2, &x, &y); a1 %= Mod, a2 %= Mod, x %= Mod, y %= Mod;
		if (n == 1) {
			printf("%llu\n", a1 * a1 % Mod);
			continue;
		}
		a.n = a.m = 4; b.n = 4, b.m = 1;
		a[1][1] = a[1][2] = a[3][2] = 1; a[2][2] = x * x % Mod; a[2][3] = y * y % Mod; a[2][4] = 2 * x * y % Mod; a[4][2] = x; a[4][4] = y;
		b[1][1] = b[3][1] = a1 * a1 % Mod; b[2][1] = a2 * a2 % Mod; b[4][1] = a2 * a1 % Mod;
		ans = qpow(a, n - 1); ans = ans * b;
		printf("%llu\n", ans[1][1]);
	}
	return 0;
}

感谢观赏！