记录编号	420443	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]矩阵游戏	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	26.518 s
提交时间	2017-07-04 19:50:51	内存使用	2.20 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
#define ll long long
#define _add(x, y) (((x) + (y)) % MOD)
#define _mul(x, y) (((ll)(x) * (ll)(y)) % MOD)
using namespace std;

const int MOD = 1000000007;
struct mat {
	int d[2][2];
	inline mat operator*(mat B) const {
		int i, j, k, t; mat R;
		for(i=0;i<2;i++) for(j=0;j<2;j++) {
			t = 0; for(k=0;k<2;k++) t = _add(t, _mul(d[i][k], B.d[k][j]));
			R.d[i][j] = t;
		}
		return R;
	}
	inline mat fpm(char *p, int len) {
		mat X = *this, T, R;
		
		R.d[0][0] = R.d[1][1] = 1;
		R.d[1][0] = R.d[0][1] = 0;
		
		int i, k;
		for(i=len-1;i>=0;i--) {
			for(k=0;k<(p[i] - '0');k++) R = R * X;
			T = X; for(k=0;k<(10-1);k++) T = T * X; X = T;
		}
		return R;
	}
};
inline void reads(char *s, int &len) {
	len = 0; char ch; while((ch = getchar()), (ch < '0' || ch > '9'));
	s[len++] = ch;
	while((ch = getchar()), (ch >= '0' && ch <= '9')) s[len++] = ch;
	s[len] = 0;
}
inline void read(int &x) {
	char ch; while((ch = getchar()), (ch < '0' || ch > '9'));
	x = ch - '0'; while((ch = getchar()), (ch >= '0' && ch <= '9')) x = x * 10 + ch - '0';
}
inline void dec(char *A, int len) {
	int k = len - 1;
	while(1) {
		if((--A[k]) >= '0') break;
		A[k] = '9'; k--;
	}
}

const int MAXL = 1000010;
char N[MAXL], M[MAXL];
int A, B, C, D, lenN, lenM;
mat MC, MR, MI, MAns;

int main() {
	freopen("matrixb.in", "rt", stdin);
	freopen("matrixb.out", "wt", stdout);

	reads(N, lenN); reads(M, lenM);
	read(A); read(B); read(C); read(D);
	MI.d[0][0] = MI.d[0][1] = 1;
	MI.d[1][0] = MI.d[1][1] = 0;

	MC.d[0][0] = 1; MC.d[0][1] = B;
	MC.d[1][0] = 0; MC.d[1][1] = A;

	MR.d[0][0] = 1; MR.d[0][1] = D;
	MR.d[1][0] = 0; MR.d[1][1] = C;

	dec(M, lenM); dec(N, lenN);
	MAns = MI * ((MC.fpm(M, lenM) * MR).fpm(N, lenN)) * MC.fpm(M, lenM);
	printf("%d", MAns.d[0][1]);
}