牛客多校第五场 B generator 1 矩阵快速幂

「爱情、让人受尽委屈。」 2021-11-11 13:58 165阅读 0赞

题意：

给定$x\_0,x\_1,a,b,n,mod, x\_i=a\*x\_\{i-1\}+b\*x\_\{i-2\}$ ,求$x\_n % mod$

**n最大有1e6*位***

题解：

矩阵快速幂。

巨大的n并不是障碍，写一个十进制的矩阵快速幂就行了。

*$ \\begin\{bmatrix\}x\_n \\\\ x\_\{n-1\} \\end\{bmatrix\}=\\begin\{bmatrix\}a &b \\\\ 1 &0 \\end\{bmatrix\} \*\\begin\{bmatrix\}x\_\{n-1\} \\\\ x\_\{n-2\} \\end\{bmatrix\}=\\begin\{bmatrix\}a &b \\\\ 1 &0 \\end\{bmatrix\}^\{n-1\}\\begin\{bmatrix\}x\_1 \\\\ x\_0 \\end\{bmatrix\} $*

#include<iostream>
    #include<cstring>
    #include<cassert>
    #define LL long long
    using namespace std;
    LL mod;
    struct Mtx{
        LL x[2][2];
        friend Mtx operator *(const Mtx &a,const Mtx &b){
            Mtx c;
            LL tmp00=a.x[0][0]*b.x[0][0] % mod+a.x[0][1]*b.x[1][0] % mod;
            LL tmp01=a.x[0][0]*b.x[0][1] % mod+a.x[0][1]*b.x[1][1] % mod;
            LL tmp10=a.x[1][0]*b.x[0][0] % mod+a.x[1][1]*b.x[1][0] % mod;
            LL tmp11=a.x[1][0]*b.x[0][1] % mod+a.x[1][1]*b.x[1][1] % mod;
            assert(tmp00>=0);
            assert(tmp01>=0);
            assert(tmp10>=0);
            assert(tmp11>=0);
            c.x[0][0]=tmp00 % mod;
            c.x[0][1]=tmp01 % mod;
            c.x[1][0]=tmp10 % mod;
            c.x[1][1]=tmp11 % mod;
            return c;
        }
        friend Mtx operator ^ (Mtx base,int n){
            Mtx ans=Mtx(1);
            while(n){
                if(n%2){
                    ans=ans*base;
                }
                base=base*base;
                n>>=1;
            }
            return ans;
        }
        Mtx(){}
        Mtx(int a){
            x[0][0]=1;
            x[1][1]=1;
            x[0][1]=0;
            x[1][0]=0;
        }
    };
    char n[1000006];
    int main(){
        LL x0,x1,a,b;
        scanf("%lld %lld %lld %lld",&x0,&x1,&a,&b);
        scanf("%s",n);
        scanf("%lld",&mod);
        int len=strlen(n);
        int kk=len-1;
        Mtx ans=Mtx(1);
        Mtx base;
        if(len==1){
            if(n[0]=='0'){
                printf("%lld\n",x0%mod);
                goto E;
            }
            if(n[0]=='1'){
                printf("%lld\n",x1%mod);
                goto E;
            }
        }
     
        while(1){
            n[kk]--;
            if(n[kk]<'0'){
                n[kk]+=10;
                kk--;
            }else break;
        }
    //  printf("%s\n",n);
        base.x[0][0]=a;
        base.x[0][1]=b;
        base.x[1][0]=1;
        base.x[1][1]=0;
        for(int i=0;i<len;i++){
            ans=ans^10;
            ans=ans*(base^(n[i]-'0'));
        }
        printf("%lld\n",(x1*ans.x[0][0]+x0*ans.x[0][1])%mod);
         
        E:return 0;
    }

小贴士：矩阵快速幂，以及一些其他的，比较复杂的，比较套路的东西，一定要封装好，这样在不太损失效率的前提下最大限度的保证了代码的可读性，这是我某次打cf时wa到自闭的教训。

转载于:https://www.cnblogs.com/isakovsky/p/11285209.html