w wyl123ly 的博客
MD

P1939 矩阵加速

3 KB 2026.10.11 原文件

P1939 矩阵加速

已知一个数列 ,它满足:

求 数列的第 项对 取余的值。

  • 对于 的数据 ,。

我们发现 ,这样我们就不能直接递推。

我们先构造答案矩阵,发现 ,那么我们就需要把 放进我们的答案矩阵。

我们的目的是把他往前推一位,得到:

行和列对应,可以得到我们的转移矩阵:

那么我们只需要对开始的:

进行 次转移即可得到答案。

#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;
}