[HNOI2011]数学作业

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
  
typedef unsigned long long Long;
  
Long n = 0;
Long m = 0;
 
Long mul(Long a,Long b)
{
    Long r = 0;
    Long M = (((Long)1LL) << 63);
    while(M)
    {
        r = (r + r) % m;
        if(b & M)
            r = (r + a) % m;
        M >>= 1;
    }
    return r;
}
 
Long pow(Long a,Long b)
{
    Long r = 1LL;
    Long M = (((Long)1LL) << 63);
    while(M)
    {
        r = mul(r,r);
        if(b & M)
            r = mul(r,a);
        M >>= 1;
    }
    return r;
}
      
struct mat
{
    Long a[5][5];
    int r;
    int c;
    mat()
    {
        clear();
    }
    void clear()
    {
        memset(a,0,sizeof(a));
        r = 0;
        c = 0;
    }
    void init_e()
    {
        clear();
        r = 3;
        c = 3;
        for(int i = 1;i <= 3;i++)
            a[i][i] = 1LL;
    }
      
    void init_l(int k = 1)
    {
        clear();
        r = 3;
        c = 3;
        a[1][1] = pow((Long)10,(Long)k);
        a[1][2] = 1;
        a[2][2] = 1;
        a[2][3] = 1;
        a[3][3] = 1;
    }
      
    void init_r()
    {
        clear();
        r = 3;
        c = 1;
        a[2][1] = 1;
        a[3][1] = 1;
    }
      
    mat operator * (const mat & B)const
    {
        mat C;
        const mat & A = (*this);
        C.r = A.r;
        C.c = B.c;
        for(int r = 1;r <= A.r;r++)
        {
            for(int c = 1;c <= B.c;c++)
            {
                for(int i = 1;i <= A.c;i++)
                {
                    C.a[r][c] += mul(A.a[r][i],B.a[i][c]);
                    C.a[r][c] %= m;
                }
            }
        }
          
        return C;
    }
  
    mat operator ^ (Long b)const
    {
        const mat & A = (*this);
        mat R;
        R.init_e();
        Long M = (((Long)1LL) << 63);
        while(M)
        {
            R = R * R;
            if(b & M)
                R = A * R;
            M >>= 1;
        }
        return R;
    }
};
  
mat A;
mat B;
mat R;
  
int main()
{
     
    std::cin>>n>>m;
     
     
    R.init_e();
    B.init_r();
     
    Long k = 1LL;
    Long last_k = 0LL; 
    int Q = 0; 
    while(n)
    {
        Q++; 
        k *= 10LL;
        Long K = k - 1;
        A.init_l(Q);
        if(n >= K)
        {
            R = (A ^ (K - last_k)) * R;
        }
        else
        {
            R = (A ^ (n - last_k)) * R;
            break;
        }
        last_k = K;
    }
     
    R = R * B;
      
    std::cout<<R.a[1][1]<<std::endl;
      
    return 0;
}