题目描述
小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：
给定正整数 N 和 M，要求计算 Concatenate (1 .. N) Mod M 的值，其中 Concatenate (1 ..N)是将所有正整数 1, 2, …, N 顺序连接起来得到的数。例如，N = 13, Concatenate (1 .. N)=12345678910111213.小C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。
解题报告:
这题还是比较简单的，很容易想到递推式:(f[i]=f[i-1]*w+i),其中(w)为i的pow(10,i的位数)
然后我们就分w为不同值讨论，然后分别用矩阵快速幂求一下即可
矩阵大概是:
[ egin{matrix}
f[i] & i & 1 \
0 & 0 & 0 \
0 & 0 & 0
end{matrix} ag{1}
]
[ egin{matrix}
w & 0 & 0 \
1 & 1 & 0 \
0 & 1 & 1
end{matrix} ag{2}
]
这里顺便吐槽一下pow这个东西，实在是太辣鸡了，在很多oj上仿佛都有问题，如果死WA的同学，可以手写了，也许就过了
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=4;
int mod;ll n,f[15];
struct mat{
ll a[N][N];
mat(){memset(a,0,sizeof(a));}
mat operator *(const mat r)const{
mat tmp;
for(int i=1;i<N;i++)
for(int j=1;j<N;j++){
for(int k=1;k<N;k++)
tmp.a[i][j]+=(a[i][k]*r.a[k][j])%mod,tmp.a[i][j]%=mod;
}
return tmp;
}
};
ll qm(ll x,ll k){
ll sum=1;
while(k){
if(k&1)sum*=x;
x*=x;k>>=1;
}
return sum;
}
void work()
{
cin>>n>>mod;
for(int i=1;i<=9;i++)
f[i]=f[i-1]*10+i,f[i]%=mod;
int m=0;ll tmp=n;
while(tmp){
m++;tmp/=10;
}
if(n<=9){
printf("%lld
",f[n]%mod);
return ;
}
ll s,t,k,last=f[9];
for(int i=1;i<m-1;i++){
s=qm(10,i);
t=(qm(10,i+1)-1);
k=t-s+1;
mat S,T;
S.a[1][1]=last;
S.a[1][2]=s;S.a[1][2]%=mod;
S.a[1][3]=1;
T.a[1][1]=t+1;T.a[1][1]%=mod;
T.a[2][1]=1;T.a[2][2]=1;T.a[3][2]=1;T.a[3][3]=1;
while(k){
if(k&1)S=S*T;
T=T*T;k>>=1;
}
last=S.a[1][1];
}
mat S,T;
t=qm(10,m-1);s=qm(10,m);
S.a[1][1]=last;
S.a[1][2]=t;S.a[1][2]%=mod;
S.a[1][3]=1;
T.a[1][1]=s;T.a[1][1]%=mod;
T.a[2][1]=1;T.a[2][2]=1;T.a[3][2]=1;T.a[3][3]=1;
k=n-t+1;
while(k){
if(k&1)S=S*T;
T=T*T;k>>=1;
}
printf("%lld
",S.a[1][1]%mod);
}
int main()
{
freopen("mathwork.in","r",stdin);
freopen("mathwork.out","w",stdout);
work();
return 0;
}