WA#9,#10,#11

代码如下

#include <bits/stdc++.h>
using namespace std	;
const int mod=1e9+7;
long long n;
struct matrix2_2{
	long long mat[3][3];
};
matrix2_2 a;
matrix2_2 b;
int mat1[2][3]={{0,0},{1,1}};
int mat2[3][3]={{0,0,0},{0,1,1},{0,1,0}};

matrix2_2 mat22x22(matrix2_2 a,matrix2_2 b){
	matrix2_2 c;
	memset(c.mat,0,sizeof(c.mat));
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			for(int k=1;k<=2;k++){
				c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
			}
		}
	}
	return c;
}
void fsp(int n){
	while(n>0){
        if(n&1) a=mat22x22(a,b);
        b=mat22x22(b,b);
        n>>=1;
    }
}
long long ans(long long n){
//	matrix2_2 a;//00
//	//			  11
//	matrix2_2 b;//000
//	//            011
//	//            010
	a.mat[1][1]=1,a.mat[1][2]=1;
	b.mat[1][1]=1,b.mat[1][2]=1,b.mat[2][1]=1;
	fsp(n-2);
	//mat22x22(a,fsp(n-2));
	return a.mat[1][1];
}

int main(){
//n=((1<<62)-1)*2+1;
scanf("%lld",&n);
if(n==1||n==2) printf("1");
else printf("%lld",ans(n));
return 0;
}