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\)
#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;
}
标签:begin,end,int,P1939,矩阵,leq,bmatrix,加速
From: https://www.cnblogs.com/wyl123ly/p/18442444