---
title: P1939 矩阵加速
type: 题解
tags:
  - 信息竞赛题解
  - 矩阵加速
  - 快速幂
---

# P1939 矩阵加速

已知一个数列 $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$ 取余的值。

- 对于 $100\%$ 的数据 $1 \leq T \leq 100$，$1 \leq n \leq 2 \times 10^9$。

我们发现 $n \le 2 \times 10 ^ 9$，这样我们就不能直接递推。

我们先构造答案矩阵，发现 $a_x=a_{x - 1} + a_{x - 3}$，那么我们就需要把 $a_x,a_{x - 1},a_{x - 2}$ 放进我们的答案矩阵。
$$
\begin{bmatrix}
a_x\\
a_{x - 1}\\
a_{x - 2}
\end{bmatrix}
$$
我们的目的是把他往前推一位，得到：
$$
\begin{bmatrix}
a_{x + 1}\\
a_{x}\\
a_{x - 1}
\end{bmatrix}
$$


行和列对应，可以得到我们的转移矩阵：
$$
\begin{bmatrix}
1 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 0\\
\end{bmatrix}
$$
那么我们只需要对开始的：
$$
\begin{bmatrix}
1\\1\\1
\end{bmatrix}
$$
进行 $n - 3$ 次转移即可得到答案。

## $code$

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int MAXN = 105;
const int X = 3;
int n;
struct Matrix{
	int a[MAXN][MAXN];
	void tox(){
		for(int i = 1;i <= X;i++){
			for(int j = 1;j <= X;j++){
				a[i][j] = 0;
			}
		}
	}
	void unifyInit(){
		a[1][1] = 1,a[1][2] = 0,a[1][3] = 0;
		a[2][1] = 0,a[2][2] = 1,a[2][3] = 0;
		a[3][1] = 0,a[3][2] = 0,a[3][3] = 1;
	}
	void Init(){
		a[1][1] = 1,a[1][2] = 0,a[1][3] = 1;
		a[2][1] = 1,a[2][2] = 0,a[2][3] = 0;
		a[3][1] = 0,a[3][2] = 1,a[3][3] = 0;
	}
	void print() const{
		cout<<"-------------------------\n";
		for(int i = 1;i <= X;i++){
			for(int j = 1;j <= X;j++){
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<"-------------------------\n";
	}
	Matrix operator*(const Matrix &other) const{
		Matrix ans;
		ans.tox();
		// print();
		// cout<<"***"<<endl;
		// other.print();
		for(int i = 1;i <= X;i++){
			for(int j = 1;j <= X;j++){
				for(int k = 1;k <= X;k++){
					ans.a[i][j] = (ans.a[i][j] + other.a[i][k] * a[k][j]) % MOD;
				}
			}
		}
		// cout<<"==="<<endl;
		// ans.print();
		return ans;
	}
	
};
Matrix qpow(Matrix x,int val){
	Matrix res;
	res.unifyInit();
	while(val){
		if(val & 1) res = res * x;
		x = x * x;
		val >>= 1;
	}
	return res;
}
Matrix m;
signed main(){
	int _;
	cin>>_;
	while(_--){
		int n;
		cin>>n;
		if(n == 1){
			cout<<1<<endl;
			continue;
		}else if(n == 2){
			cout<<1<<endl;
			continue;
		}else if(n == 3){
			cout<<1<<endl;
			continue;
		}
		m.Init();
		// m.print();
		m = qpow(m,n - 3);
		// m.print();
		int ans = 0;
		for(int i = 1;i <= X;i++){
			ans = (ans + m.a[1][i]) % MOD;
		}
		cout<<ans<<endl;
	}
	return 0;
}
```
