求问:
查看原帖
求问:
929151
xxr___楼主2025/1/19 10:42

这个题我这么做为什么要调用 ksm(n-1) ?

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pre(i,l,r) for(int i=l;i>=r;--i)
const int mod=1e9+7;
const int N=10;
struct matrix{
	int c[N][N];
	void clear(){
		rep(i,1,3) rep(j,1,3) c[i][j]=0; 
	}
};
matrix operator ^(const matrix &a,const matrix &b){
	matrix ans;ans.clear();
	rep(i,1,3){
		rep(j,1,3){
			rep(k,1,3){
				ans.c[i][j]+=a.c[i][k]*b.c[k][j];
				ans.c[i][j]%=mod;
			}
		}
	}
	return ans;
}
int ksm(int y){
	matrix ans;ans.clear();
	matrix x;x.clear();
	x.c[1][1]=1;x.c[1][3]=1;
	x.c[2][1]=1;x.c[3][2]=1;
	ans.c[1][1]=1;ans.c[2][1]=1;
	ans.c[3][1]=1;
	while(y){
		if(y&1){
			ans=ans^x;
		}
		x=x^x;y>>=1;
	}
	return ans.c[1][1];
}
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t,n;
	cin>>t;
	rep(i,1,t){
		cin>>n;
		if(n<=3){
			cout<<1<<'\n';
		}else cout<<ksm(n-1)<<'\n';
	}
	return 0;
}
2025/1/19 10:42
加载中...