为什么别人的代码都是用n-2
走快速幂,而我的却必须得用n-1
走快速幂
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n;
struct matrix{
int a[10][10];
matrix(){
memset(a,0,sizeof(a));
}
inline void set(){
a[1][1]=a[1][2]=a[2][1]=1;
a[2][2]=0;
}
inline void build(){
a[1][1]=a[2][1]=1;
}
}a,ans;
int read(){
int s=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+(ch-'0');
ch=getchar();
}
return s*f;
}
matrix operator *(const matrix &x,const matrix &y){
matrix z;
for(int k=1;k<=2;k++){
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
}
}
}
return z;
}
signed main(){
a.set(),ans.build();
n=read();
if(n<=2){
cout<<1<<endl;
return 0;
}
n-=1;
while(n>0){
if(n&1){
ans=ans*a;
}
n/=2;
a=a*a;
}
cout<<ans.a[1][1]%mod<<endl;
return 0;
}