这题折腾死人啦_(:зゝ∠)_
首先看这题第一眼：(⊙v⊙)嗯，找规律？
然而题目告诉我：1≤N≤1018且1≤M≤109
这不太对吧，好像是N<=10^18 , M<=10^9
(⊙o⊙)…怎么还有模？？？
好吧，那么logn的算法就只有快速幂了（倍增被我吃了233）
好的，那么我们来想一想递推方程，递推方程还是很好写出来的。
很好，递推式出来了，接着我们构造矩阵
接着问题就来了_( Д)ノ
我们平时做的矩阵快速幂根本没有这个奇怪的$10^{len(n)}$的奇怪的变量啊，怎么搞ヽ(*。>Д<)o゜
回到数据范围：N≤1018 N<=10^18
log的时间复杂度绰绰有余，那么我们能否把$10^{len(n)}$变成常数？
当然可以，我们枚举位数，从1位数枚举到n的位数，对每一个位数进行矩阵快速幂。
(⊙v⊙)嗯，理论很简单，实际实现呢？
从每一位到每一位的衔接可以折腾死人，而且对于最后的n的位数并不是整的，细节处理可以使人上天 凸(艹皿艹 )
具体步骤：
①枚举位数 ②构造矩阵 ③计算矩阵
注意事项：不要使用log10函数计算位数，不要使用pow函数计算次方，因为这些在long long范围内都会爆炸
代码如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
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;
}
