求讲解
查看原帖
求讲解
131610
luo_shen楼主2021/5/15 13:17

为什么别人的代码都是用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;
}
2021/5/15 13:17
加载中...