矩阵快速幂

把指数按十进制拆开的快速幂。。。

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}LL x0, x1, a, b, p;string n;struct Matrix{    LL m[2][2];    Matrix(){        full(m, 0);    }    Matrix operator * (Matrix &a){        Matrix ret;        for(int i = 0; i < 2; i ++){            for(int j = 0; j < 2; j ++){                for(int k = 0; k < 2; k ++){                    ret.m[i][j] = ret.m[i][j] + (m[i][k] * a.m[k][j] % p);                    if(ret.m[i][j] >= p) ret.m[i][j] -= p;                }            }        }        return ret;    }};Matrix ori, t, e;inline void init(){    e.m[0][0] = e.m[1][1] = 1;    ori.m[0][0] = x1, ori.m[1][0] = x0;    t.m[0][0] = a, t.m[0][1] = b, t.m[1][0] = 1;}inline Matrix fpow(Matrix &a, const string &n){    Matrix ret = e;    for(int i = n.size() - 1; i >= 0; i --){        int y = n[i] - '0';        while(y --) ret = ret * a;        Matrix tr = a * a;        a = tr * tr;        a = a * a * tr;        //for(int j = 1; j <= 9; j ++) a = a * tr;    }    return ret;}int main(){    __fastIn;    cin >> x0 >> x1 >> a >> b;    cin >> n >> p;    init();    t = fpow(t, n);    ori = t * ori;    cout << (ori.m[1][0] % p) << endl;    return 0;}