矩阵专题
先看道板子题
初始化 F1 F2 F3 进行n-1次加速以后 变成 Fn Fn+1 Fn+2
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int mod=1e9+7;
struct node{
ll m[5][5];
}ans,base;
int T;
node mul(node a,node b){
node res;
memset(res.m,0,sizeof(res.m));
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
res.m[i][j]=(res.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;
return res;
}
ll fast_mi(int b){
node res;
memset(res.m,0,sizeof(res.m));
for(int i=1;i<=3;i++)
res.m[i][i]=1;
memset(base.m,0,sizeof(base.m));
base.m[1][1]=base.m[1][3]=base.m[2][1]=base.m[3][2]=1;
while(b){
if(b&1)res=mul(res,base);
base=mul(base,base);
b>>=1;
}
return res.m[1][1];
}
void solve();
int main(){
cin>>T;
while(T--)solve();
return 0;
}
void solve(){
int n;
cin>>n;
cout< 同理来计算斐波那契数
有个有趣的公式 gcd(f(n),f(m))=f(gcd(n,m))
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int mod=1e9+7;
struct node{
ll m[5][5];
}ans,base;
int T;
node mul(node a,node b){
node res;
memset(res.m,0,sizeof(res.m));
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
res.m[i][j]=res.m[i][j]+a.m[i][k]*b.m[k][j];
return res;
}
ll fast_mi(int b){
node res;
memset(res.m,0,sizeof(res.m));
for(int i=1;i<=2;i++)
res.m[i][i]=1;
memset(base.m,0,sizeof(base.m));
base.m[1][1]=base.m[1][2]=base.m[2][1]=1;
while(b){
if(b&1)res=mul(res,base);
base=mul(base,base);
b>>=1;
}
return res.m[1][1];
}
void solve();
int main(){
cin>>T;
while(T--)solve();
return 0;
}
void solve(){
int n;
cin>>n;
cout<