洛谷-1939
思路
原来我是打算按照斐波那契数列的方法，找到一个二维矩阵，因为\(a_x = a_{x-1} + a_{x-3}\)，只有两个元素。
但是错了，得不到正确答案。
再看题解，全都是三维矩阵，我就感觉，是不是初始条件的个数决定矩阵是几维的呢？
比如：\(f_n = f_{n-1} + f_{n-2}\)，初始条件需要\(f_1\)和\(f_2\)。
比如：\(a_x = a_{x-1} + a_{x-3}\)，初始条件需要\(a_1\)、\(a_2\)和\(a_3\)。
以上均为猜测，不知道如何说明。
由斐波那契数列的做法
\[\begin{pmatrix} f_n&f_{n-1} \end{pmatrix} = \begin{pmatrix} f_{n-1} & f_{n - 2} \end{pmatrix} * \begin{pmatrix} a & b \\ c & d \end{pmatrix} \]猜测本题做法
\[\begin{pmatrix} a_n & a_{n-1} & a_{n - 2} \end{pmatrix} = \begin{pmatrix} a_{n-1} & a_{n - 2} & a_{n - 3} \end{pmatrix} * S \tag{1} \]其中
\[S = \begin{pmatrix} A & B & C \\ D & E & F \\ G & H & I \end{pmatrix} \]将\((1)\)中的矩阵乘法展开，得
\[\begin{cases} a_n = a_{n - 1} * A + a_{n - 2} * D + a_{n - 3} * G \\ a_{n-1} = a_{n - 1} * B + a_{n - 2} * E + a_{n - 3} * H \\ a_{n-2} = a_{n - 1} * C + a_{n - 2} * F + a_{n - 3} * I \end{cases} \tag{2} \]由于\(a_x = a_{x-1} + a_{x-3}\)，故可以将\((2)\)中第一个方程的\(a_n\)换掉，得
\[\begin{cases} a_{n-1} + a_{n-3} = a_{n - 1} * A + a_{n - 2} * D + a_{n - 3} * G \\ a_{n-1} = a_{n - 1} * B + a_{n - 2} * E + a_{n - 3} * H \\ a_{n-2} = a_{n - 1} * C + a_{n - 2} * F + a_{n - 3} * I \end{cases} \tag{3} \]由\((3)\)可得
\[S = \begin{pmatrix} A = 1 & B = 1 & C = 0 \\ D = 0 & E = 0 & F = 1 \\ G = 1 & H = 0 & I = 0 \end{pmatrix} \]然后就能通过矩阵快速幂得到答案。
首先有
\[\begin{pmatrix} f_{n + 2} & f_{n + 1} & f_n \end{pmatrix} = \begin{pmatrix} f_{n + 1} & f_{n} & f_{n - 1} \end{pmatrix} * S = \dots = \begin{pmatrix} f_3 & f_2 & f_1 \end{pmatrix} * S^{(n - 1)} \]由于\(n \geq 1\)，因此可以愉快地做题了，由矩阵乘法可得答案就是\(f_n = S[0][2] + S[1][2] + S[2][2]\)。（矩阵下标从0开始）
Code
#include <bits/stdc++.h>
using namespace std;
#define _u_u_ ios::sync_with_stdio(false), cin.tie(nullptr)
#define cf int _o_o_;cin>>_o_o_;for (int Case = 1; Case <= _o_o_;Case++)
#define SZ(x) (int)(x.size())
inline void _A_A_();
signed main() {_A_A_();return 0;}
using ll = long long;
#define int long long
int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 3, M = 5010;
const int inf = 0x3f3f3f3f;
int n;
struct mat
{
int m[N][N];
};
mat operator * (const mat&a,const mat&b ) {
mat c;
memset(c.m, 0, sizeof c.m);
for (int i = 0;i < N;i++) {
for (int j = 0;j < N;j++) {
for (int k = 0;k < N;k++) {
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
}
}
}
return c;
}
mat qpow(mat a, int n) {
mat c;
memset(c.m, 0, sizeof c.m);
for (int i = 0;i < N;i++) c.m[i][i] = 1;
while (n) {
if (n & 1) {
c = c * a;
}
a = a * a;
n >>=1;
}
return c;
}
inline void _A_A_() {
#ifdef LOCAL
freopen("in.in", "r", stdin);
#endif
_u_u_;
mat s;
cf {
memset(s.m, 0, sizeof s.m);
s.m[0][0] = s.m[0][1] = s.m[1][2] = s.m[2][0] = 1;
cin >> n;
s = qpow(s, n - 1);
cout << (s.m[0][2] + s.m[1][2] + s.m[2][2]) % mod << "\n";
}
}