题解 P3216 【[HNOI2011]数学作业】

· · 题解

题意

## 题解 对与位数相同的数，用$k$表示位数，用$f[x]$表示从$10^k$一直写到$x$的值，则有: $$ f[x]=f[x-1]\times 10^{k+1}+x\pmod m $$ 就相当于在原串上拼接了$x$，但看到$1\le n \le 10^{18}$的数据范围~~当场就放弃了~~，很明显我们必须优化上面的柿子，不然程序能T飞到天上去 这里我们需要引入矩阵乘法的概念 >矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的列数（column）和第二个矩阵的行数（row）相同时才有意义 [1] 。一般单指矩阵乘积时，指的便是一般矩阵乘积。一个$m×n$的矩阵就是$m×n$个数排成$m$行$n$列的一个数阵。由于它把许多数据紧凑地集中到了一起，所以有时候可以简便地表示一些复杂的模型，如电力系统网络模型。 [2] --百度百科 >设$A$为$m\times p$ 的矩阵，$B$为$p\times n$ 的矩阵，那么称$m\times n$的矩阵$C$为矩阵$A$与$B$的乘积，记作 $C=AB$，其中矩阵C中的第 $i$行第$j$ 列元素可以表示为：$(AB)_{ij}=\sum_{k=1}^pa_{ik}b_{kj}

很明显：

f[x+1]&=&f[x]\times 10^{k+1} &+x&+1 \\ x+1&=&0 &+x&+1 \\ 1&=&0 &+0&+1 \\ \end{matrix}

那么矩阵也很容易构造了

\text{设}P=\begin{bmatrix} 10^{k+1}&1&1\\ 0 &1&1\\ 0&0&1 \end{bmatrix} \begin{pmatrix} g[x]\\ x\\ 1 \end{pmatrix} =P\times \begin{pmatrix} g[x-1]\\ x-1\\ 1 \end{pmatrix} =P \times P \times \begin{pmatrix} g[x-2]\\ x-2\\ 1 \end{pmatrix} = \dots= P^{x-10^k}\times \begin{pmatrix} 10^k\\ 10^k\\ 1 \end{pmatrix}

对于由于矩阵也有结合律，式中用快速幂处理P的次方就行了

代码

 //#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
namespace in{
    char buf[1<<21],*p1=buf,*p2=buf;
    inline int getc(){
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
    }
    template <typename T>inline void read(T& t){
        t=0;int f=0;char ch=getc();
        while (!isdigit(ch)){
            if(ch=='-')f = 1;
            ch=getc();
        }
        while(isdigit(ch)){
            t=t*10+ch-48;
            ch = getc();
        }
        if(f)t=-t;
    }
    template <typename T,typename... Args> inline void read(T& t, Args&... args){
        read(t);read(args...);
    }
}
namespace out{
    char buffer[1<<21];
    int p1=-1;
    const int p2 = (1<<21)-1;
    inline void flush() {
        fwrite(buffer,1,p1+1,stdout),
        p1=-1;
    }
    inline void putc(const char &x) {
        if(p1==p2)flush();
        buffer[++p1]=x;
    }
    template <typename T>void write(T x) {
        static char buf[15];
        static int len=-1;
        if(x>=0){
            do{
                buf[++len]=x%10+48,x/=10;
            }while (x);
        }else{
            putc('-');
            do {
                buf[++len]=-(x%10)+48,x/=10;
            }while(x);
        }
        while (len>=0)
            putc(buf[len]),--len;
    }
}
//fread快读快输
//让你的代码看上去更高级（逃 
#define int unsigned long long
using namespace std;
int mod;
struct mat{//矩阵
    int m,n;//矩阵的行数、列数
    int a[10][10];
    int *operator[](const int i){
        return a[i];
    }
    mat(){
        memset(a,0,sizeof a);
        m=n=3;
    }
    mat(int hang,int lie,int *num){
        m=hang,n=lie;
        for(int i=1,tot=0;i<=hang;i++)
            for(int j=1;j<=lie;j++)
                a[i][j]=num[tot++];
    } 
    mat(int hang,int lie){
        m=hang,n=lie;
        memset(a,0,sizeof a);
    } 
    mat operator*(mat b)const{//重载乘号 
        //保证n=b.m
        mat c(m,b.n);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=b.n;j++)
        for(int k=1;k<=m;k++) 
            c[i][j]+=a[i][k]*b[k][j]%mod,c[i][j]%=mod;
        return c;
    }
};
int n;
mat fpow(mat a,int b){//矩阵快速幂 
    int tmp[]={1,0,0,0,1,0,0,0,1};//单位矩阵 
    mat ans(3,3,tmp);
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;b>>=1;
    }return ans;
}
int fpow(int a,int b){//整数快速幂 
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }return ans;
}
int ans=0,already=0;
//   答案 已有位数 
#define pow lpow
int lpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;b>>=1;
    }return ans;

}
signed main(){
    in::read(n,mod);
    for(int k=0;pow(10,k)<=n;k++){//枚举K 
        //printf("%d\n",k);
        int t[]={fpow(10,k),fpow(10,k),1};
        mat tmp(3,1,t);
        int tt[]={fpow(10,k+1),1,1,0,1,1,0,0,1};
        mat p(3,3,tt);
        //printf(" %lld\n",(min(pow(10,k+1),n+1)-pow(10,k))*(k+1));
        ans*=fpow(10,(min((int)pow(10,k+1),n+1)-(int)pow(10,k))*(k+1));
        ans%=mod;
        //printf(" %lld\n",min((int)pow(10,k+1)-1,n)-(int)pow(10,k));
        ans+=((fpow(p,(int)min((int)pow(10,k+1)-1,n)-(int)pow(10,k))*tmp))[1][1];
        ans%=mod;
    }
    out::write(ans);
    out::flush();
    return 0;
}

其实这题思维难度并不大，只是代码细节有点多