记录编号	304386	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	13.078 s
提交时间	2016-09-08 13:06:29	内存使用	2.20 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int p=1000000007,N=1000010;
struct matrix{
	long long a[2][2];
	matrix(){memset(a,0,sizeof a);}
	matrix(int A,int b,int c,int d){
		a[0][0]=A;a[0][1]=b;
		a[1][0]=c;a[1][1]=d;
	}
	bool empty(){
		return (a[0][0]|a[0][1]|a[1][0]|a[1][1])==0;
	}
	matrix operator * (const matrix &x){
		if (empty()) return x;
		matrix ans;
		for (int i=0;i<2;i++)
		for (int j=0;j<2;j++)
		for (int k=0;k<2;k++)
			ans.a[i][j]=(ans.a[i][j]+a[i][k]*x.a[k][j])%p;
		return ans;
	}
}ans(1,1,1,1),Mi,x,y;
matrix mi(matrix x,char *s){
	int l=strlen(s);
	matrix ans,m[11];
	for (int i=l-1;i>=0;i--){
		for (int j=1;j<10;j++) m[j]=m[j-1]*x;
		if (s[i]>'0') ans=ans*m[s[i]-'0'];
		x=m[9]*x;
	}
	return ans;
}
char n[N],m[N];
int a,b,c,d,ln,lm;
int main()
{
	freopen("matrixb.in","r",stdin);
	freopen("matrixb.out","w",stdout);
	scanf("%s%s%d%d%d%d",n,m,&a,&b,&c,&d);
	int i=strlen(n)-1,j=strlen(m)-1;
	while (n[i]=='0') n[i]='9',i--;n[i]--;
	while (m[j]=='0') m[j]='9',j--;m[j]--;
	x=matrix(a,0,b,1);Mi=mi(x,m);
	ans=ans*Mi;
	x=matrix(c,0,d,1)*Mi;
	ans=ans*mi(x,n);
	printf("%lld\n",ans.a[0][0]);
	return 0;
}