Q：矩阵加速（数列）
已知一个数列 \(a\)，它满足：
\[a_x=
\begin{cases}
1 & x \in\{1,2,3\}\\
a_{x-1}+a_{x-3} & x \geq 4
\end{cases}
\]
求 \(a\) 数列的第 \(n\) 项对 \(10^9+7\) 取余的值。
我会暴力！
但是时间复杂度 \(O(n)\)，数据范围 \(n\leq 2\times 10^9\)
如何优化？
矩阵加速！\(O(\log n)\)
快速幂大家应该都会了吧
前置知识：矩阵
相当于二维数组了（先行后列）
怎么运算呢？
-
矩阵加减法：对应位置上的数相加减即可。
-
矩阵乘法：\(A\) 的列数 = \(B\) 的行数，
\[C_{i,j}=\displaystyle \sum_{k = 1}^m A_{i,k}\times B_{k,j}
\]
如何加速？
关键是先要构造矩阵。
如何构造矩阵？
题解的方法太秒了，直接放在下面了：
我们首先要确定目标矩阵。下面这个矩阵就是我想要的矩阵.
\[\begin{bmatrix}F[i]\\F[i-1]\\F[i-2]\end{bmatrix}
\]
那么这个矩阵要怎样算出来。根据题目给出的递推式可以得到下面三个式子
\[f[i] = f[i-1] \times 1 + f[i-2] \times 0 + f[i-3] \times 1
\]
\[f[i-1] = f[i-1] \times 1 + f[i-2] \times 0 + f[i-3] \times 0
\]
\[f[i-2] = f[i-1] \times 0 + f[i-2] \times 1 + f[i-3] \times 0
\]
通过每一项的系数可以得出初始矩阵为
\[\begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}
\]
然后我们就可以通过矩阵快速幂进行求解。
值得注意的是，这个矩阵的 \(N\) 次方算出来的第一个元素是 \(F[N+1]\) ,这样的话我们可以直接在输出的时候输出第二行第一个元素。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3;
int n, m = 1e9 + 7, T;
void mul(int c[], int a[], int b[][N]) {
int temp[N] = {0};
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
temp[i] = (temp[i] + (ll)a[j] * b[j][i]) % m;
memcpy(c, temp, sizeof temp);
}
void mul(int c[][N], int a[][N], int b[][N]) {
int temp[N][N] = {0};
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
temp[i][j] = (temp[i][j] + (ll)a[i][k] * b[k][j]) % m;
memcpy(c, temp, sizeof temp);
}
int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
int f1[N] = {1, 1, 1}, a[N][N] = {
{1, 0, 1},
{1, 0, 0},
{0, 1, 0}
};
cin >> n, n--;
while (n) {
if (n & 1) mul(f1, f1, a); // res = res * a
mul(a, a, a), n >>= 1; // a = a * a
} // qmi
cout << f1[1] << '\n';
}
return 0;
}