90 pts 求条(马蜂良好)
查看原帖
90 pts 求条(马蜂良好)
1398636
yezhengjie0000001楼主2025/7/26 17:50
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d;	
string s1,s2;
ll oul;
ll A[101][101],T[101][101];
ll ans[101][101];
ll n=2;
void f(){
	ll C[101][101]={0};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				C[i][j]=(C[i][j]+ans[i][k]*A[k][j])%oul;
				//cout<<ans[i][k]<<' '<<A[k][j]<<' ';
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans[i][j]=C[i][j];
		}
	}
	//cout<<'\n';
}
void h(){
	ll C[101][101]={0};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				C[i][j]=(C[i][j]+A[i][k]*ans[k][j])%oul;
				//cout<<ans[i][k]<<' '<<A[k][j]<<' ';
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans[i][j]=C[i][j];
		}
	}
	//cout<<'\n';
}
void g(){
	ll C[101][101]={0};
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				C[i][j]=(C[i][j]+A[i][k]%oul*A[k][j]%oul)%oul;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			A[i][j]=C[i][j];
		}
	}
}
void qpow(ll p){
	while(p){
		if(p%2){
			f();
		}
		g();
		p/=2;
	}
}
ll mm,nn,tem;
int main(){
	oul=1e9+7;
	if(a==1||c==1){
		oul--;
	}
	cin>>s1>>s2>>a>>b>>c>>d;
	for(int i=0;i<s1.size();i++){
		nn=(nn*10%(oul-1)+s1[i]-'0'+oul-1)%(oul-1);	
	}
	for(int i=0;i<s2.size();i++){
		mm=(mm*10%(oul-1)+s2[i]-'0'+oul-1)%(oul-1);
	}
	ans[1][1]=ans[2][2]=1;
	A[1][1]=a,A[2][1]=b,A[1][2]=0,A[2][2]=1;
	mm=(mm-1+oul)%oul;
	nn=(nn-1+oul)%oul;
	qpow(mm);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			A[i][j]=ans[i][j];
			T[i][j]=ans[i][j];
		}
	}
	ans[1][1]=c,ans[1][2]=0,ans[2][1]=d,ans[2][2]=1;
	h();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			A[i][j]=ans[i][j];
		}
	}
	ans[1][1]=ans[2][2]=1;
	ans[1][2]=0;
	ans[2][1]=0;
	qpow(nn);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			A[i][j]=T[i][j];
		}
	}
	f();
	cout<<(ans[1][1]+ans[2][1]+oul)%oul<<'\n';
	return 0;
}
2025/7/26 17:50
加载中...