这题是一道假紫题

题目描述

小 C 数学成绩优异，于是老师给小 C 留了一道非常难的数学作业题：

给定正整数 NN 和 MM ，要求计算Concatenate (1 .. N)Concatenate(1..N) ModMod MM 的值，其中 Concatenate (1 .. N)Concatenate(1..N) 是将所有正整数 1, 2, …, N1,2,…,N 顺序连接起来得到的数。例如，N = 13N=13 , Concatenate (1 .. N)=12345678910111213Concatenate(1..N)=12345678910111213 .小C 想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

输入输出格式

输入格式：

 

从文件input.txt中读入数据，输入文件只有一行且为用空格隔开的两个正整数N和M，其中30%的数据满足1≤N≤10000001≤N≤1000000 ；100%的数据满足1≤N≤10^{18}1≤N≤1018 且1≤M≤10^91≤M≤109 .

 

输出格式：

 

输出文件 output.txt 仅包含一个非负整数，表示 Concatenate (1 .. N)Concatenate(1..N) ModMod MM 的值。

 

输入输出样例

输入样例#1： 

13 13

输出样例#1： 

4

这道题的思路非常好想，就是长成这样的一个矩阵

这道题与以往的矩阵有一些区别

1.它带了一个常数i，和一个1，这个很好理解，因为i是每次都加一的，这样才能维护

2.矩阵的[0,0]不是一定的，是会变的，所以会使这道题细节处理的让人上天

放一下矩乘的模板（个人喜欢重载运算符，比较方便）；

1 struct matrix{ 2     ll m[3][3]; 3     friend matrix operator*(matrix a,matrix b) 4     { 5         matrix fina; 6         clear(fina.m,0); 7         for(int i=0;i<3;i++) 8             for(int j=0;j<3;j++) 9                 for(int k=0;k<3;k++)10                     fina.m[i][j]=(fina.m[i][j]%mod+ksc(a.m[i][k]%mod,b.m[k][j]%mod))%mod;11         return fina;12     }13     friend matrix operator^(matrix a,ll k)14     {15         matrix fina;16         clear(fina.m,0);17         fina.m[0][0]=fina.m[1][1]=fina.m[2][2]=1;18         while(k)19         {20             if(k%2)fina=fina*a;21             k=k/2,a=a*a;22         }23         return fina;24     }25 }key,im,aaa;

 

注意

1.要用龟速乘，要开longlong，不要吝惜内存

2.矩阵一定要清零，必要的赋成单位矩阵

然后就A啦

1 #include"cstdio" 2 #include"algorithm" 3 #include"cstring" 4 #define clear(a,val) memset(a,val,sizeof(a)) 5 typedef long long ll; 6 ll n,mod,len; 7 ll ksc(ll a,ll b) 8 { 9     ll fina=0;10     while(b)11     {12         if(b%2)fina=(fina+a)%mod;13         b>>=1,a=(a+a)%mod;14     }15     return fina%mod;16 }17 struct matrix{18     ll m[3][3];19     friend matrix operator*(matrix a,matrix b)20     {21         matrix fina;22         clear(fina.m,0);23         for(int i=0;i<3;i++)24             for(int j=0;j<3;j++)25                 for(int k=0;k<3;k++)26                     fina.m[i][j]=(fina.m[i][j]%mod+ksc(a.m[i][k]%mod,b.m[k][j]%mod))%mod;27         return fina;28     }29     friend matrix operator^(matrix a,ll k)30     {31         matrix fina;32         clear(fina.m,0);33         fina.m[0][0]=fina.m[1][1]=fina.m[2][2]=1;34         while(k)35         {36             if(k%2)fina=fina*a;37             k=k/2,a=a*a;38         }39         return fina;40     }41 }key,im,aaa;42 void chai(ll n){
     while(n)len++,n/=10;}43 int main()44 {45     scanf("%lld%lld",&n,&mod);46     chai(n);ll temp=0;47     clear(key.m,0),clear(im.m,0),clear(aaa.m,0);48     key.m[1][0]=key.m[2][0]=key.m[1][1]=key.m[2][1]=key.m[2][2]=1;49     im.m[0][0]=im.m[1][1]=im.m[2][2]=1;50     aaa.m[0][0]=aaa.m[0][1]=aaa.m[0][2]=1;51     for(ll i=1;i<=len;i++)52     {53         if(temp*10>n)54         {55             key.m[0][0]=ksc(temp%mod,10)%mod;56             im=im*(key^(n-temp+1));57         }58         else 59         {60             if(temp==0)key.m[0][0]=10%mod,im=im*(key^8),temp=(ll)10;61             else key.m[0][0]=temp*10%mod,im=im*(key^(temp*10-temp)),temp*=10;62         }63     }64     aaa=aaa*im;65     printf("%lld\n",aaa.m[0][0]%mod);66     return 0;67 }

 

 By 浅夜_MISAKI