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