题目描述

小 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为不同值讨论，然后分别用矩阵快速幂求一下即可

矩阵大概是:

\[ \begin{matrix} f[i] & i & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} \tag{1} \]

\[ \begin{matrix} w & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} \tag{2} \]

这里顺便吐槽一下pow这个东西，实在是太辣鸡了，在很多oj上仿佛都有问题，如果死WA的同学，可以手写了，也许就过了

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #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
          
           >=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\n",f[n]%mod); return ; } ll s,t,k,last=f[9]; for(int i=1;i
           
            >=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\n",S.a[1][1]%mod);}int main(){ freopen("mathwork.in","r",stdin); freopen("mathwork.out","w",stdout); work(); return 0;}