C++14(g++5.4) 解法, 执行用时: 1821ms, 内存消耗: 1388K, 提交时间: 2019-08-02 15:51:37

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;
struct node{
	ll mat[2][2];
};
ll x0,x1,a,b,mod;
node ans,O,tmp,z;
char n[N];
node cal(node x,node y){
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			z.mat[i][j]=0;
			for(int k=0;k<2;k++){
				z.mat[i][j]=(z.mat[i][j]+x.mat[i][k]*y.mat[k][j])%mod;
			}
		}
	}
	return z;
}
int main(){
	int op;scanf("%lld %lld %lld %lld %s %lld",&x0,&x1,&a,&b,n,&mod);
	int len=strlen(n);ans.mat[0][0]=ans.mat[1][1]=1;
	tmp.mat[0][0]=a;tmp.mat[0][1]=b;tmp.mat[1][0]=1;
	for(int i=len-1;i>=0;i--){
		op=n[i]-'0';
		for(int j=0;j<op;j++)ans=cal(ans,tmp);
		O.mat[0][0]=O.mat[1][1]=1;
		O.mat[1][0]=O.mat[0][1]=0;
		for(int j=0;j<10;j++)O=cal(O,tmp);
		tmp=O;
	}
	printf("%lld\n",(x1*ans.mat[1][0]+x0*ans.mat[1][1])%mod);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1557ms, 内存消耗: 32652K, 提交时间: 2019-08-01 20:37:39

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1000005;
LL mod;
struct MAT{
	LL t[2][2];
	MAT operator * (const MAT&b)const{
		MAT res;
		memset(res.t,0,sizeof(res.t));
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++){
			res.t[i][j]=(res.t[i][j]+t[i][k]*b.t[k][j]%mod)%mod;
		}return res;
	}
}a,b[N];

char s[1000005];
int main(){
	scanf("%lld%lld%lld%lld%s%lld",&a.t[0][0],&a.t[0][1],&b[0].t[1][1],&b[0].t[0][1],s+1,&mod);
	b[0].t[1][0]=1;
	int l=strlen(s+1);
	for(int i=l;i>=1;i--){
		b[l-i+1]=b[l-i];
		MAT tmp=b[l-i];
		for(int j=1;j<=9;j++){
			if(s[i]-'0'==j)a=a*b[l-i+1];
			b[l-i+1]=b[l-i+1]*tmp;
		}
	}
	printf("%lld\n",a.t[0][0]);
	return 0;
}