题目描述
小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：
给定正整数 \(n,m\)，要求计算 \(\text{Concatenate}(n) \bmod \ m\) 的值，其中
\(\text{Concatenate}(n)\) 是将 \(1 \sim n\) 所有正整数 顺序连接起来得到的数。
例如，\(n = 13\) , \(\text{Concatenate}(n) = 12345678910111213\)。小C
想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。输入格式
一行两个正整数 \(n,m\)。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
13 13样例输出 #1
4提示
【数据范围】 对于 \(30\%\) 的数据，\(1\le n \le 10^6\)； 对于 \(100\%\) 的数据，\(1\le n \le 10^{18}\)，\(1\le m \le 10^9\)。
不会就暴力
对于我这个蒟蒻，首先想到的竟然不是暴力。看到题，我以为是一道纯纯的数学题，是可以推出来的，然鹅。经过半个小时的尝试，这真的是一道不可能手算出来的题目
然后我就开始暴力了
暴力代码
#include<bits/stdc++.h>
using namespace std;
long long n,mod,ans=0;
int wei(long long x){
int s=0;
while(x>0){
s++;
x/=10;
}
return s;
}
long long kuaisumi(int a,int b){
long long sum=1;
for(;b;b>>=1){
if(b&1){
sum=(long long)sum*a;
}
a=(long long)a*a;
}
return sum;
}
int main(){
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
scanf("%lld%lld",&n,&mod);
for(long long i=1;i<=n;i++){
ans=(ans*kuaisumi(10,wei(i))+i)%mod;
}
cout<<ans;
return 0;
}
直接开始递推，每次统计需要加上的位数，每次都取模，最后就得出答案了
暴力记得写好看一点，可以骗到40分 比30分还多
正解
记得刚才说的递推吗？那么有办法将递推的时间减小吗？当然就是矩阵快速幂了
矩阵快速幂
我们在进行普通的递推过程中，会同时出现加法和乘法，就例如此题中的：
ans=(ans*kuaisumi(10,wei(i))+i)%mod;
这时候我们没有办法使用普通的快速幂算法，因为普通的快速幂只能有乘法，例如：
long long kuaisumi(int a,int b){
long long sum=1;
for(;b;b>>=1){
if(b&1){
sum=(long long)sum*a;
}
a=(long long)a*a;
}
return sum;
}
这时候，我们就要利用矩阵乘法
什么是矩阵乘法
这里是一个直观地解释
本题思路
我们这样定义矩阵
struct Matrix{
int h,l;
long long a[5][5];
}ans,wns;
l代表列数，h代表行数
在这道题中，我们将ans定义在一个矩阵中,并初始化
但是为了在后面的计算中更加方便，我们将它定义成方阵，空余位都填上0
在这个矩阵中，第一位使我们的答案，第二位是当前枚举到需要添加在后面的数，最后以为是用来进行转移的固定数
之后我们需要定义一个转移矩阵，这里直接给出
这里的k代表当前需要在后面添加的数的位数，当我们按照矩阵乘法将转移矩阵乘上ans矩阵，就可以得到每一次递推的答案。当然，要记得取模。
我们知道，矩阵乘法满足结合律（具体请百度），那么我们可以把每一次乘以转移矩阵的过程合并位求转移矩阵的幂，而求幂的过程我们就可以用到矩阵快速幂来提速了
其实矩阵快速幂和普通快速幂的思路是一样的，只是把数字换成了矩阵
对于矩阵乘法的实现，我们可以重载运算符*，但是因为我比较懒，就单独写了两个函数，分别是矩阵乘法和矩阵快速幂
Matrix time(Matrix r,Matrix c){
Matrix timesans;
memset(timesans.a,0,sizeof(timesans.a));
timesans.h=r.h;
timesans.l=c.l;
for(int i=1;i<=r.h;i++){
for(int j=1;j<=c.l;j++){
for(int q=1;q<=r.l;q++){
timesans.a[i][j]=(timesans.a[i][j]+r.a[i][q]%mod*c.a[q][j]%mod)%mod;
}
}
}
return timesans;
}
Matrix mul(Matrix x,long long y){
Matrix res;
res.h=res.l=3;
memset(res.a,0,sizeof(res.a));
for(int i=1;i<=3;i++){
res.a[i][i]=1;
}
for(;y;y>>=1){
if(y&1) res=time(x,res);
x=time(x,x);
}
return res;
}
在拥有了所有必须的函数后，我们就开始求解
求解答案
普通的矩阵快速幂中，一般转移矩阵是不会改变的，但是在此题中，转移矩阵的第一项会随着添加的数的位数而改变，所以在过程中，我们需要分段求解，每一次分段时，更新转移矩阵
for(int i=1;;i++){
wns.a[1][1]=v[i]%mod;
long long tot=min(n,v[i]-1)-v[i-1]+1;
Matrix val=mul(wns,tot);
val.l=val.h=3;
ans=time(ans,val);
if(v[i]-1>=n)
break;
}
其中v数组时预处理的10的i次方
我们要将段分为1-9，10-99，100-999……
在这一段程序中，tot代表的时我们此次需要枚举的次数，其中的min是用来判断我们当前枚举的是否大于了需要枚举的最大值n，如果大于了，那就直接枚举到n，而不是下一个分段
这就是所有的思路了
最终代码
#include<bits/stdc++.h>
using namespace std;
struct Matrix{
int h,l;
long long a[5][5];
}ans,wns;
long long n,mod;
long long v[25];
Matrix time(Matrix r,Matrix c){
Matrix timesans;
memset(timesans.a,0,sizeof(timesans.a));
timesans.h=r.h;
timesans.l=c.l;
for(int i=1;i<=r.h;i++){
for(int j=1;j<=c.l;j++){
for(int q=1;q<=r.l;q++){
timesans.a[i][j]=(timesans.a[i][j]+r.a[i][q]%mod*c.a[q][j]%mod)%mod;
}
}
}
return timesans;
}
Matrix mul(Matrix x,long long y){
Matrix res;
res.h=res.l=3;
memset(res.a,0,sizeof(res.a));
for(int i=1;i<=3;i++){
res.a[i][i]=1;
}
for(;y;y>>=1){
if(y&1) res=time(x,res);
x=time(x,x);
}
return res;
}
int main(){
ans.l=ans.h=wns.h=wns.l=3;
cin>>n>>mod;
v[0]=1;
for(int i=1;i<=18;i++){
v[i]=v[i-1]*10;
}
ans.a[1][1]=0,ans.a[1][2]=1,ans.a[1][3]=1;
wns.a[2][1]=wns.a[2][2]=wns.a[3][2]=wns.a[3][3]=1;
for(int i=1;;i++){
wns.a[1][1]=v[i]%mod;
long long tot=min(n,v[i]-1)-v[i-1]+1;
Matrix val=mul(wns,tot);
val.l=val.h=3;
ans=time(ans,val);
if(v[i]-1>=n)
break;
}
printf("%lld",ans.a[1][1]%mod);
return 0;
}
注意
不开long long见祖宗
原文地址：http://www.cnblogs.com/GXYZY/p/16869483.html
