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

· · 题解

这题折腾死人啦_(:зゝ∠)_

首先看这题第一眼：(⊙v⊙)嗯，找规律？

然而题目告诉我：1≤N≤1018且1≤M≤109

这不太对吧，好像是N<=10^18，M<=10^9

(⊙o⊙)…怎么还有模？？？

好吧，那么logn的算法就只有快速幂了

（倍增被我吃了233）

好的，那么我们来想一想递推方程，递推方程还是很好写出来的。

f[n]=f[n-1] \times 10^{len(n)}+n

很好，递推式出来了，接着我们构造矩阵

\begin{pmatrix} f[n] & n & 1 \end{pmatrix} = \begin{pmatrix} f[n-1] & n-1 & 1 \end{pmatrix} \times \begin{bmatrix} 10^{len(n)} & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} =\begin{pmatrix} f[1] & 1 & 1 \end{pmatrix} \times \begin{bmatrix} 10^{len(n)} & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}^{n-1}

接着问题就来了_( ﾟДﾟ)ﾉ

我们平时做的矩阵快速幂根本没有这个奇怪的10^{len(n)}的奇怪的变量啊，怎么搞ヽ(*。>Д<)o゜

回到数据范围：N≤1018 N<=10^18

log的时间复杂度绰绰有余，那么我们能否把10^{len(n)}变成常数？

当然可以，我们枚举位数，从1位数枚举到n的位数，对每一个位数进行矩阵快速幂。

(⊙v⊙)嗯，理论很简单，实际实现呢？

从每一位到每一位的衔接可以折腾死人，而且对于最后的n的位数并不是整的，细节处理可以使人上天 凸(艹皿艹 )

具体步骤：

①枚举位数 ②构造矩阵 ③计算矩阵

注意事项：不要使用log10函数计算位数，不要使用pow函数计算次方，因为这些在long long范围内都会爆炸

代码如下

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
    LL num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
const int maxn=5;
LL mod;
struct Matrix {
    LL n,m,a[maxn][maxn];
    Matrix(LL n,LL m) {
        this->n=n;
        this->m=m;
        memset(a,0,sizeof(a));
    }
    Matrix(LL n,LL m,char E) { //单位矩阵
        this->n=n;
        this->m=m;
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++)a[i][i]=1;
    }
    LL* operator [] (const LL x) {
        return a[x];
    }
    Matrix operator * (Matrix b) {
        Matrix c(n,b.m);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=b.m; j++)
                for(int k=1; k<=m; k++)
                    c[i][j]=(c[i][j]+a[i][k]%mod*b[k][j]%mod)%mod;
        return c;
    }
    void operator *= (Matrix& b) {
        *this=*this*b;
    }
    Matrix operator ^ (LL b) {
        Matrix ans(n,m,'e'),a=*this;
        while(b>0) {
            if(b&1)ans=ans*a;
            a*=a;
            b>>=1;
        }
        return ans;
    }
};
LL n;
int Get_Len(LL x) {
    int len=0;
    while(x) {
        len++;
        x/=10;
    }
    return len;
}
LL pow10(int x) {
    LL ans=1;
    for(int i=1; i<=x; i++)ans*=10;
    return ans;
}
int main() {
    n=Get_Int();
    mod=Get_Int();
    Matrix A(1,3);
    int len=Get_Len(n);
    A[1][1]=A[1][2]=A[1][3]=1;
    for(int i=0; i<len-1; i++) { //枚举位数
        Matrix B(3,3);
        B[1][1]=pow10(i+1)%mod;
        B[2][1]=B[2][2]=B[3][1]=B[3][2]=B[3][3]=1;
        LL m=pow10(i+1)-pow10(i);
        A=A*(B^(m-(i==0?1:0)));
    }
    Matrix B(3,3);
    B[1][1]=pow10(len)%mod;
    B[2][1]=B[2][2]=B[3][1]=B[3][2]=B[3][3]=1;
    LL m=n-pow10(len-1)+1;
    A=A*(B^(m-(len-1==0?1:0)));
    printf("%lld\n",A[1][1]);
    return 0;
}