2019牛客暑期多校训练营（第五场） B generator 1（十进制矩阵快速幂）

题意：

分析：十进制快速幂板子题。

代码（模板）：

#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;
}