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

题意：给定x0，x1，a，b，满足xi=a*xi-1+b*xi-2； 求xn，n<10^(10^6)；

思路：10进制快速幂裸题。降幂来写好像也是可以的，但是循环节不是phi(mod)，所以数学不好就还是用10进制快速幂吧。

10进制快速幂：复杂度O(n*log10*K^3)； 复杂度也不低，所以要尽量少做mod运算。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll Mod;

inline ll mul(ll x,ll y,ll p){

  return x*y%p;

}

struct mat

{

    ll M[][];

    mat() { M[][]=M[][]=M[][]=M[][]=; }

    mat friend operator *(mat a,mat b)

    {

        mat res;

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

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

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

           res.M[i][j]+=a.M[i][k]*b.M[k][j];//每次取mod复杂度会过高。

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

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

           res.M[i][j]%=Mod;

        return res;

    }

    mat friend operator ^(mat a,int x)

    {

       mat res; res.M[][]=res.M[][]=1LL;

       while(x){

          if(x&) res=res*a; a=a*a; x/=;

       } return res;

    }

};

char c[];int x[];

int main()

{

    int T; ll X0,X1,A,B,N;

    T=;

    while(T--){

        scanf("%lld%lld%lld%lld",&X0,&X1,&A,&B);

        scanf("%s%lld",c+,&Mod);

        int len=strlen(c+);

        for(int i=;i<=len;i++) x[i]=c[i]-'';

        x[len]--;

        for(int i=len;i>=;i--){

            if(x[i]<) x[i-]--,x[i]+=;

        }

        mat base,a,ans;

        ans.M[][]=ans.M[][]=;

        base.M[][]=A%Mod; base.M[][]=B%Mod; base.M[][]=1LL;

        a.M[][]=X1%Mod,a.M[][]=X0%Mod;

        for(int i=len;i>=;i--){

             if(x[i]) ans=ans*(base^x[i]);

             base=base^;

        }

        ans=ans*a;

        printf("%lld\n",ans.M[][]%Mod);

    }

    return ;

}