2019 牛客暑期多校 B generator 1 （矩阵快速幂+倍增）

题目：https://ac.nowcoder.com/acm/contest/885/B

题意：给你x0,x1，让你求出xn，递推式时xn=a*xn-1+b*xn-2

思路：这个n特别大，我自己没有摸清欧拉降幂的性质，瞎套了，然后其实因为底数是一个矩阵，并不能运用这一定理，但是这个n又这么大，我们就可以使用倍增

这里用2倍增有点麻烦，我们就直接用10倍增，然后这个递推式很明显就能看出是一个2*2的矩阵快速幂，然后求解即可

#include<bits/stdc++.h>

#define maxn 1000005

using namespace std;

typedef long long ll;

ll x0,x1,a,b,mod;

ll mod1;

char str[maxn];

char s[maxn];

struct jz//结构体写法的矩阵快速幂

{

    long long num[][];

    jz() { memset(num,,sizeof(num)); }

    jz(ll a,ll b,ll c,ll d){

        num[][]=a;

        num[][]=b;

        num[][]=c;

        num[][]=d;

    };

    jz operator*(const jz &P)const {

        jz ans;

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

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

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

                    ans.num[i][j]=(ans.num[i][j]+num[i][k]*P.num[k][j]%mod)%mod;

        return ans;

    }

}COE,ans,unit;

int T_T;

jz F, A;

jz B, T;

jz pOw(jz X,long long m)//矩阵快速幂

{

    jz ans;

    ans.num[][]=;

    ans.num[][]=;

    for(;m;m>>=,X=X*X)

        if(m&)

            ans=ans*X;

    return ans;

}

int main(){

    scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b);

    scanf("%s%lld",str,&mod);

    unit=jz(x1,x0,,);

    COE=jz(a,,b,);

    for(int i=strlen(str)-;i>=;i--){//倍增

        unit=unit*pOw(COE,str[i]-'');

        COE=pOw(COE,);

    }

    printf("%lld",unit.num[][]);

}