Description
定义序列a的通项公式为$a_i=left{egin{aligned}1 && i leq 3 \a_{i-1}+a_{i-3} && i geq 4end{aligned} ight.$
求序列a的第n项对1e9+7取模的值
Solution
由于n的值很大，所以普通的递推无法解决，我们考虑使用矩阵乘法
假设$F(n)=egin{bmatrix}a_n & a_{n-1} & a_{n-2}end{bmatrix}$，我们考虑将$F(n-1)$乘上一个矩阵base之后变成$F(n)$
也就是说$egin{bmatrix}a_{n-1} & a_{n-2} & a_{n-3}end{bmatrix} imes base = egin{bmatrix}a_n & a_{n-1} & a_{n-2}end{bmatrix}$
显然，我们可以轻易计算出$base=egin{bmatrix}1 & 1 & 0 \0 & 0 & 1 \ 1 & 0 & 0 end{bmatrix}$
我们定义初始矩阵$a=egin{bmatrix}1 & 1 & 1 end{bmatrix}$，然后利用矩阵快速幂计算$a imes base^{n-3}$即可
时间复杂度为$O(3^3log_2n)$
Code
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int mod = 1e9 + 7; 5 int T, n; 6 struct Matrix { 7 ll m[4][4]; 8 Matrix() {memset(m, 0, sizeof(m));} 9 Matrix operator *(const Matrix &x) const { 10 Matrix ret; 11 for (register int i = 1; i <= 3; ++i) 12 for (register int j = 1; j <= 3; ++j) 13 for (register int k = 1; k <= 3; ++k) 14 ret.m[i][j] = (ret.m[i][j] + m[i][k] * x.m[k][j] % mod) % mod; 15 return ret; 16 } 17 } a, base; 18 inline void init() { 19 base.m[1][1] = 1; base.m[1][2] = 1; base.m[1][3] = 0; 20 base.m[2][1] = 0; base.m[2][2] = 0; base.m[2][3] = 1; 21 base.m[3][1] = 1; base.m[3][2] = 0; base.m[3][3] = 0; 22 a.m[1][1] = 1; a.m[1][2] = 1; a.m[1][3] = 1; 23 } 24 void qpow(int p) { 25 while (p) { 26 if (p & 1) a = a * base; 27 base = base * base; 28 p >>= 1; 29 } 30 } 31 int main() { 32 scanf("%d", &T); 33 while (T--) { 34 init(); 35 scanf("%d", &n); 36 if (n <= 3) { 37 puts("1"); continue ; 38 } 39 qpow(n - 3); 40 printf("%lld ", a.m[1][1]); 41 } 42 return 0; 43 }