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

· · 题解

第一篇题解！QwQ~

*这道题首先是要明白矩阵快速幂的作用：将1e18的N转换为可以用快速幂做的快速运算。。。

*其次是本题蒟蒻认为的一个坑点——被MOD过的LL类型的相乘虽然感觉上是不会“爆炸”的，但在本题和一些其它的矩阵类型题中是很有可能的，所以很需要一个Q_Mul函数来快速乘，防止LL类型爆炸。。。

*还有一个本题的坑点——需要将Ten的Ten[0]，即0位数设为1，详情请看代码。

*本题的一个难点——需要用A[20]来存储每一中位数所需要的A矩阵

例如：若Ans此时为两位数，那我我们就需要一个A[2],即{{LL,LL,LL,LL},{LL,10^2,1,1},{LL,0,1,1},{LL,LL,0,1}}来作为 Ans乘的对象，是的Ans乘以A[2]了之后可以得到Ans的下一次处理后的数。

（代码有点。。。）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath> 

#define INF 0x3f3f3f3f
using namespace std;

long long Total,MOD;

inline long long Q_Mul(long long L,long long R,long long P)
{
    L=(L%P+P)%P; 
    R=(R%P+P)%P;
    long long Res=L*R-(long long)((long double)L/P*R+1e-8)*P; 
    return Res < 0?Res+P:Res;  
}//快速乘，防止LL爆炸

struct Node{
    long long Squ[4][4];

    inline void Clear_S(long long X)
    {
        for(int i=1;i<=3;i++)
          for(int j=1;j<=3;j++)
            Squ[i][j]=X;
    }//清空Node用

    friend Node operator * (Node A,Node B){
        Node Get;
        Get.Clear_S(0);
        for(int i=1;i<=3;i++)
          for(int j=1;j<=3;j++)
            for(int k=1;k<=3;k++){
                Get.Squ[i][j]=(Get.Squ[i][j]%MOD+Q_Mul(A.Squ[i][k],B.Squ[k][j],MOD))%MOD;
            }
        return Get;
    }//重载矩阵乘法，即两矩阵相乘

}A[20],Ans;//需要用来转换的矩阵以及我们的Ans

long long Ten[20];//其实没什么用，初始化A时可以用

inline long long read()
{
    unsigned long long x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}//快读，emm。。。

inline long long Fpow(long long x,long long y)
{
    long long step=x;
    long long ans=1;
    while(y){
        if(y&1)ans=ans*step;
        y>>=1;
        step=step*step;
    }
    return ans;
}//快速幂，算Ten时用

inline void Sta()
{
    Total=read();MOD=read();
    for(int i=1;i<=19;i++){ 
        Ten[i]=Fpow(10,i);
        A[i].Clear_S(1);
        A[i].Squ[2][1]=0;A[i].Squ[1][1]=Ten[i];
        A[i].Squ[3][1]=0;A[i].Squ[3][2]=0;
    }//每一位数的A初始化
    Ans.Clear_S(0);
    Ans.Squ[3][1]=1;//Ans的初始化emm。。。
    Ten[0]=1;//嗯
}//初始化

inline void Node_Pow(int X)
{
    long long Sum;
    if(X==(floor(log10(Total))+1)) Sum=(Total-Ten[X-1]+1);
    else Sum=Ten[X]-Ten[X-1];//每次需要完成的快幂数Sum
    while(Sum){
        if(Sum&1) Ans=A[X]*Ans;
        Sum>>=1;
        A[X]=A[X]*A[X];
    }//矩阵快速幂
}

int main()
{
    Sta();//整体初始化（蒟蒻的习惯）
    for(int i=1;i<=floor(log10(Total))+1;i++){
        Node_Pow(i);//完成每一位数的矩阵快速幂
    }
    printf("%lld",Ans.Squ[1][1]);//输出答案
    return 0;
}

*非常OJBKQwQ~