2019牛客暑期多校训练营（第五场）- B generator 1 （齐次线性递推+矩阵快速幂）...

r囧r小猫 2021-10-30 02:36 195阅读 0赞

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

题意：已知齐次线性式xn=a\*xn-1+b\*xn-2，已知a，b，x0，x1，求xn，n很大，n<=1010^6.

思路：矩阵快速幂模板题，构造矩阵t:

a b
    1 0

矩阵ans：

x1 0
    x0 0

显然ans1=t×ans,ans1为：

x2 0
    x1 0

那么ansn=t^n\*ans，ansn为：

xn+1 0
    xn   0

所以用矩阵快速幂计算t^n，n很大，快速幂要用十进制倍增，对每一位的计算不能直接乘，还要用二进制的快速幂，不然会TLE。

最近写代码像中邪了一样，照着别人的代码写总会有个小地方写错，然后找一天的错误，连续几天了。

AC代码：

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
     
    typedef long long LL;
    LL x0,x1,a,b;
    int MOD;
    char s[1000005];
     
    struct Matrix{
        LL a[2][2];
        Matrix(){memset(a,0,sizeof(a));}
        Matrix operator * (const Matrix y){
            Matrix ret;
            for(int i=0;i<2;++i)
                for(int j=0;j<2;++j)
                    for(int k=0;k<2;++k)
                        ret.a[i][j]=(ret.a[i][j]+a[i][k]*y.a[k][j])%MOD;
            return ret;
        }
        void operator = (const Matrix y){
            for(int i=0;i<2;++i)
                for(int j=0;j<2;++j)
                    a[i][j]=y.a[i][j];
        }
    }tmp;
     
    Matrix qpow2(Matrix m,int b){
        Matrix ret=tmp;
        ret.a[0][0]=ret.a[1][1]=1;
        while(b){
            if(b&1) ret=ret*m;
            m=m*m;
            b>>=1;
        }
        return ret;
    }
     
    Matrix qpow10(Matrix m,char *s){
        Matrix ret=tmp;
        ret.a[0][0]=ret.a[1][1]=1;
        for(int i=strlen(s)-1;i>=0;--i){
            int num=s[i]-'0';
            ret=ret*qpow2(m,num);
            m=qpow2(m,10);
        }
        return ret;
    }
     
    int main(){
        scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b);
        scanf("%s%d",s,&MOD);
        Matrix t,ans;
        t.a[0][0]=a,t.a[0][1]=b,t.a[1][0]=1,t.a[1][1]=0;
        ans.a[0][0]=x1,ans.a[0][1]=0,ans.a[1][0]=x0,ans.a[1][1]=1;
        t=qpow10(t,s);
        ans=t*ans;
        printf("%lld\n",ans.a[1][0]);
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/11370331.html