bzoj2326 [HNOI2011]数学作业

矩阵乘，按位搞
两个矩阵，分别为
a n s 00 i 00 100
10 k 11 011001
快速幂转移就好了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define LL long long
using namespace std;
LL n,p,poww[22],ans,cnt,a[4][4],b[4][4];
void mpow(LL A[4][4],LL B[4][4],LL C[4][4]){
    LL D[4][4];
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++){
            D[i][j]=0;
            for(int k=1;k<=3;k++)
                D[i][j]=(LL)(A[i][k]*B[k][j]%p+D[i][j]+p)%p;
        }
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            C[i][j]=D[i][j];
}
void print(LL A[4][4]){
    for (int i = 1; i < 4; ++i)
    {
        for (int j = 1; j < 4; ++j)
            printf("%d ",A[i][j]);
        printf("
");
    }
}
void qpow(LL k){
    LL A[4][4]={0};
    A[1][1]=A[2][2]=A[3][3]=1;
    while(k){
        if(k&1) mpow(A,b,A);
        mpow(b,b,b);k>>=1;
    }
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            b[i][j]=A[i][j];
}
LL getnum(LL x){
    LL tot=0;
    while(x){tot++;x/=10;}
    return tot;
}
int main(){
    poww[0]=1;
    for(int i=1;i<=18;i++)poww[i]=poww[i-1]*10;
    scanf("%lld%lld",&n,&p);
    cnt=getnum(n);
    a[1][1]=a[1][2]=0;a[1][3]=1;
    b[1][1]=10;b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;
    for(int i=1;i<cnt;i++){
        b[1][1]=poww[i]%p;b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;
        qpow(poww[i]-poww[i-1]);
        mpow(a,b,a);
    }
    b[1][1]=poww[cnt]%p;b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;
    qpow(n-poww[cnt-1]+1);
    mpow(a,b,a);
    printf("%lld
",a[1][1]);
    return 0;
}