十进制快速幂（牛客多校第五场）-- generator 1

思路：

十进制快速幂。

 #include <stdio.h>//sprintf

 #include <cstdlib>////malloc  exit strcat itoa system("cls")

 #include <iostream>//pair

 #include <fstream>

 #include <bitset>

 //#include <map>   https://ac.nowcoder.com/acm/contest/885/B

 #include <vector>

 #include <stack>

 #include <set>

 #include <string.h>//strstr

 #include <string>

 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;

 #include <cmath>

 #include <queue>//priority_queue<long long, vector<long long>, greater<long long> > q;

 #include <vector>

 //#include <math.h>

 //#include <windows.h>   https://www.nitacm.com/problem_show.php?pid=222

 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 using namespace std;

 #define pr printf

 #define sc scanf

 #define fo(a,b,c) for((a)=(b);(a)<=(c);(a)++)//register long long i

 #define fr(a,b,c) for((a)=(b);(a)>=(c);(a)--)

 #define mem(a,b) memset((a),(b),sizeof((a)))

 const double e=2.718281828;

 const double PI=acos(-1.0);

 const double ESP=1e-;

 const long long inf=;

 const long long N=;

 long long mod;

 const long long MAXN=;

 long long x0,x1,a,b,MOD;

 struct MAT

 {

     long long mat[MAXN][MAXN];

     MAT()

     {

         mat[][]=mat[][]=;//对角矩阵 E;

         mat[][]=mat[][]=;

     }

     MAT operator*(const MAT &a)const

     {

         MAT b;

         long long i,j,k;

         mem(b.mat,);

         fo(i,,MAXN-)

         {

             fo(j,,MAXN-)

             {

                 fo(k,,MAXN-)

                 {

                     b.mat[i][j]=(b.mat[i][j]+mat[i][k]*a.mat[k][j]);

                     b.mat[i][j]%=mod;

                 }

             }

         }

         return b;

     }

 }transfer;

 MAT Mqpow(MAT x,long long n)

 {

     struct MAT temp;

     while(n)

     {

         if(n&)

             temp=temp*x;

         x=x*x;

         n>>=;

     }

     return temp;

 }

 char n[N];

 struct MAT mark[],start;

 int main()

 {

     sc("%lld%lld%lld%lld%s%lld",&x0,&x1,&a,&b,n,&MOD);

 //    mem(transfer.mat,0);

     mod=MOD;

     transfer.mat[][]=a,transfer.mat[][]=b;

     transfer.mat[][]=,transfer.mat[][]=;

     start.mat[][]=x1,start.mat[][]=x0;

     mark[]=transfer;

     for(int i=;i<=;++i)

         mark[i]=transfer*mark[i-];

     int l=strlen(n);

     struct MAT ans;

     for(int i=;i<=l-;++i)

     {

         ans=Mqpow(ans,);

         ans=ans*mark[n[i]-''];

     }

     start=ans*start;

     pr("%lld\n",start.mat[][]%MOD);

     return ;

 }