记录编号	154700	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.144 s
提交时间	2015-03-24 06:27:12	内存使用	4.13 MiB

#include <iostream>
#include <cstdio>
#include <cstring>

typedef unsigned long long int64;

const int64 p=1000000007ULL;

using namespace std;

void Mread(int64 &x){
	char ch;
	while(ch=getchar(),!isdigit(ch));
	x=ch-'0';
	while(ch=getchar(),isdigit(ch)){
		x=10LL*x+(int64)(ch-'0');
		if(x>=(p-1)) x%=(p-1);
	}
}

struct MA{
	int n,m;
	int64 a[3][3];
	inline void init(int nt,int mt){
		n=nt; m=mt;
		memset(a,0,sizeof(a));
	}
	inline MA operator*(const MA &x)const{
		MA re; re.init(n,x.m);
		int i,j,k;
		for(i=1;i<=re.n;i++)
			for(j=1;j<=re.m;j++)
				for(k=1;k<=m;k++){
					re.a[i][j]+=a[i][k]*x.a[k][j];
					if(re.a[i][j]>=p) re.a[i][j]%=p;
				}
		return re;
	}
	inline void print(){
		cout<<"Matrix : "<<n<<' '<<m<<endl;
		int i,j;
		for(i=1;i<=n;i++){
			for(j=1;j<=m;j++)
				cout<<a[i][j]<<' ';
			cout<<endl;
		}
	}
}A,B,Ans;

int64 n,m;
char s1[2000010],s2[2000010];

inline MA qpow(const MA &x,int64 n){
	MA re,tp=x; re.init(2,2);
	for(int i=1;i<=2;i++) re.a[i][i]=1LL;
	for(;n;n>>=1,tp=tp*tp) if(n&1) re=re*tp;
	return re;
}

int main(){
	freopen("matrixb.in","r",stdin);
	freopen("matrixb.out","w",stdout);
	scanf("%s%s",s1,s2);
	int64 mo=p-1;
	A.init(2,2);
	B.init(2,2);
	Ans.init(1,2);
	Ans.a[1][1] = Ans.a[1][2] = 1;
	A.a[2][2] = B.a[2][2] = 1;
	scanf("%llu%llu%llu%llu",
		&A.a[1][1],&A.a[2][1],&B.a[1][1],&B.a[2][1]);
	if(A.a[1][1]==1&&B.a[1][1]==1) mo=p;
	n=0;
	for(int i=0,ln=strlen(s1);i<ln;i++)
		n=(10LL*n+s1[i]-'0')%mo;
	m=0;
	for(int i=0,ln=strlen(s2);i<ln;i++)
		m=(10LL*m+s2[i]-'0')%mo;
	if(n==0) n=mo;
	if(m==0) m=mo;
	A=qpow(A,m-1);
	B=A*B;
	B=qpow(B,n-1);
	B=B*A;
	Ans=Ans*B;
	printf("%llu\n",Ans.a[1][1]);
	return 0;
}