比赛 2022级数学专题练习赛1 评测结果 AAAAAAAAAAWWWWWWWWWW
题目名称 矩阵游戏 最终得分 50
用户昵称 op_组撒头屯 运行时间 0.004 s
代码语言 C++ 内存使用 1.31 MiB
提交时间 2022-12-12 21:12:36
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
struct sdf{
	ll p[2][2];
	sdf(){
		for (int i=0;i<=1;i++){
			for (int j=0;j<=1;j++)p[i][j]=0;
		}
	}
	sdf operator*(const sdf&x){
		sdf tmp;
		for (int i=0;i<=1;i++){
			for (int j=0;j<=1;j++){
				for (int k=0;k<=1;k++){
					tmp.p[i][j]=(tmp.p[i][j]+p[i][k]*x.p[k][j]%mod)%mod;
				}
			}
		}
		return tmp;
	}
}A,B,C,D,E,bs; 
ll n,m,a,b,c,d;
void fst1(ll x){
	if (!x){
		C=bs;return ;
	}
	if (x&1){
		fst1(x-1);C=C*A;
	}
	else{
		fst1(x/2);C=C*C;
	}
}
void fst2(ll x){
	if (!x){
		E=bs;return ;
	}
	if (x&1){
		fst2(x-1);E=E*D;
	}
	else{
		fst2(x/2);E=E*E;
	}
}
int main(){
	freopen ("matrixb.in","r",stdin);
	freopen ("matrixb.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld%lld",&m,&n,&a,&b,&c,&d);
	A.p[0][0]=a;A.p[0][1]=b;A.p[1][0]=0;A.p[1][1]=1;
	B.p[0][0]=c;B.p[0][1]=d;B.p[1][0]=0;B.p[1][1]=1;
	bs.p[0][0]=bs.p[1][1]=1;bs.p[0][1]=bs.p[1][0]=0;
	fst1(n-1);
	D=C*B;
	fst2(m-1);
	E=E*C;
	ll ans=(E.p[0][0]+E.p[0][1])%mod;
	printf("%lld\n",ans);
	return 0;
}