BZOJ 2326: [HNOI2011]数学作业(矩阵乘法)

传送门

解题思路

　　NOIp前看到的一道题，当时想了很久没想出来，NOIp后拿出来看竟然想出来了。注意到有递推\(f[i]=f[i-1]*poww[i]+i\)，\(f[i]\)表示\(1-i\)连接起来组成的数字，\(poww[i]\)表示\(10\)的\(i\)的位数次幂，发现这个可以用矩阵快速幂优化，\([f[i],i+1,1]\)，转移到\([f[i+1],i+2,1]\)，要做\(n\)的位数次快速幂，每次修改一下转移矩阵中\(poww\)的值就行了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long

using namespace std;
typedef long long LL;

LL n,ans,poww[20]={1};
int MOD,wei;

struct Matrix{
    LL a[4][4];
    void clear(){memset(a,0,sizeof(a));}
    friend Matrix operator*(const Matrix A,const Matrix B){
        Matrix ret;ret.clear();
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                for(int k=1;k<=3;k++)
                    (ret.a[i][j]+=(LL)A.a[i][k]*B.a[k][j]%MOD)%=MOD;
        return ret;
    }
}pre,A;

Matrix fast_pow(Matrix x,LL y){
    Matrix ret;ret.clear();ret.a[1][1]=ret.a[2][2]=ret.a[3][3]=1;
    for(;y;y>>=1){
        if(y&1) ret=ret*x;
        x=x*x;
    }
    return ret;
}

signed main(){
    scanf("%lld%lld",&n,&MOD);LL nn=n;
    while(n) n/=10,wei++;
    for(int i=1;i<=18;i++) poww[i]=poww[i-1]*10;
    A.a[2][1]=A.a[2][2]=A.a[3][2]=A.a[3][3]=1;pre.a[1][2]=pre.a[1][3]=1;
    for(int i=1;i<wei;i++) {
        A.a[1][1]=poww[i]%MOD;
        pre=pre*fast_pow(A,poww[i]-poww[i-1]);
    }A.a[1][1]=poww[wei]%MOD;
    pre=pre*fast_pow(A,nn-poww[wei-1]+1);
    printf("%lld\n",pre.a[1][1]);
    return 0;
}

BZOJ 2326: [HNOI2011]数学作业(矩阵乘法)

原文：https://www.cnblogs.com/sdfzsyq/p/10092996.html