构造一个单位矩阵
然后构造下面这个矩阵
\[\left(\begin{array}{ccc}10 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)\]然后往后面加一位数，就相当于将这个矩阵乘了一次
这样做完了1~9，下面处理10~99
构造下面这个矩阵
\[\left(\begin{array}{ccc}100 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)\]这样做完了10~99，下面处理100~999
构造下面这个矩阵
\[\left(\begin{array}{ccc}1000 & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1\end{array}\right)\]……以此类推，共乘n次，最后加上快速幂即可
4ms AC
AC-Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long N,MOD;
struct Mat{
long long A[3][3];
}S[20],ans;
Mat operator * (Mat a,Mat b)
{
Mat ret;
ret.A[0][0]=(a.A[0][0]*b.A[0][0]+a.A[0][1]*b.A[1][0]+a.A[0][2]*b.A[2][0])%MOD;
ret.A[0][1]=(a.A[0][0]*b.A[0][1]+a.A[0][1]*b.A[1][1]+a.A[0][2]*b.A[2][1])%MOD;
ret.A[0][2]=(a.A[0][0]*b.A[0][2]+a.A[0][1]*b.A[1][2]+a.A[0][2]*b.A[2][2])%MOD;
ret.A[1][0]=(a.A[1][0]*b.A[0][0]+a.A[1][1]*b.A[1][0]+a.A[1][2]*b.A[2][0])%MOD;
ret.A[1][1]=(a.A[1][0]*b.A[0][1]+a.A[1][1]*b.A[1][1]+a.A[1][2]*b.A[2][1])%MOD;
ret.A[1][2]=(a.A[1][0]*b.A[0][2]+a.A[1][1]*b.A[1][2]+a.A[1][2]*b.A[2][2])%MOD;
ret.A[2][0]=(a.A[2][0]*b.A[0][0]+a.A[2][1]*b.A[1][0]+a.A[2][2]*b.A[2][0])%MOD;
ret.A[2][1]=(a.A[2][0]*b.A[0][1]+a.A[2][1]*b.A[1][1]+a.A[2][2]*b.A[2][1])%MOD;
ret.A[2][2]=(a.A[2][0]*b.A[0][2]+a.A[2][1]*b.A[1][2]+a.A[2][2]*b.A[2][2])%MOD;
return ret;
}
void init()
{
S[1].A[0][0]=10%MOD;
S[1].A[1][0]=1;
S[1].A[1][1]=1;
S[1].A[2][0]=1;
S[1].A[2][1]=1;
S[1].A[2][2]=1;
ans.A[0][0]=1;
ans.A[1][1]=1;
ans.A[2][2]=1;
for (int i=2;i<20;i++)
{
S[i]=S[i-1];
S[i].A[0][0]*=10;
S[i].A[0][0]%=MOD;
}
}
Mat Ksm(Mat a,long long k)
{
Mat ret;
ret.A[0][0]=ret.A[1][1]=ret.A[2][2]=1;
if (k==0)
return ret;
if (k==1)
return a;
if (k%2==0)
{
ret=Ksm(a,k/2);
return ret*ret;
}else
{
ret=Ksm(a,k-1);
return ret*a;
}
}
int main()
{
long long begin=1,i,nn,len=0,k=1;
scanf("%lld%lld",&N,&MOD);
init();
nn=N;
while (nn)
{
nn/=10;
len++;
}
for (i=1;i<len;i++)
{
ans=ans*Ksm(S[i],k*9);
k*=10;
}
ans=ans*Ksm(S[len],N-k+1);
printf("%lld\n",ans.A[2][0]);
return 0;
}