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

题意：

给定$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[][];

    friend Mtx operator *(const Mtx &a,const Mtx &b){

        Mtx c;

        LL tmp00=a.x[][]*b.x[][] % mod+a.x[][]*b.x[][] % mod;

        LL tmp01=a.x[][]*b.x[][] % mod+a.x[][]*b.x[][] % mod;

        LL tmp10=a.x[][]*b.x[][] % mod+a.x[][]*b.x[][] % mod;

        LL tmp11=a.x[][]*b.x[][] % mod+a.x[][]*b.x[][] % mod;

        assert(tmp00>=);

        assert(tmp01>=);

        assert(tmp10>=);

        assert(tmp11>=);

        c.x[][]=tmp00 % mod;

        c.x[][]=tmp01 % mod;

        c.x[][]=tmp10 % mod;

        c.x[][]=tmp11 % mod;

        return c;

    }

    friend Mtx operator ^ (Mtx base,int n){

        Mtx ans=Mtx();

        while(n){

            if(n%){

                ans=ans*base;

            }

            base=base*base;

            n>>=;

        }

        return ans;

    }

    Mtx(){}

    Mtx(int a){

        x[][]=;

        x[][]=;

        x[][]=;

        x[][]=;

    }

};

char n[];

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-;

    Mtx ans=Mtx();

    Mtx base;

    if(len==){

        if(n[]==''){

            printf("%lld\n",x0%mod);

            goto E;

        }

        if(n[]==''){

            printf("%lld\n",x1%mod);

            goto E;

        }

    }

    while(){

        n[kk]--;

        if(n[kk]<''){

            n[kk]+=;

            kk--;

        }else break;

    }

//  printf("%s\n",n);

    base.x[][]=a;

    base.x[][]=b;

    base.x[][]=;

    base.x[][]=;

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

        ans=ans^;

        ans=ans*(base^(n[i]-''));

    }

    printf("%lld\n",(x1*ans.x[][]+x0*ans.x[][])%mod);

    E:return ;

}

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

8月6日PS:这种概念叫做DRY原则，全称是Don't repeat yourself.今天刚学到的名词。

巴特西

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

最新文章

热门文章