题目描述

Description

题目分析

直接计算不好搞 我们来考虑将每一位分开
也就是说 计算1~9 10~99 100~999 1000~9999 ..... 10^k ~ n
每一块的计算是递推式子 由于N过大可以用矩乘加速递推

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long n,m;
int kl;
struct your
{
    long long x[10][10];
    your() { memset(x,0,sizeof x); }
    friend your operator*(your x,your y)
    {
        your z;
        for(int i=1;i<=kl;i++)
            for(int j=1;j<=kl;j++)
                for(int k=1;k<=kl;k++)
                    z.x[i][j]=(z.x[i][j]+x.x[i][k]*y.x[k][j]%m)%m;
        return z;
    }
}A,B;
void ksm(long long y)
{
    kl=3;
    while(y)
    {
        if(y&1) A=A*B;
        y>>=1,B=B*B;
    }
}
long long po[20];
void work(long long x,long long y,int t)
{
    //printf("%lld %lld\n",x,y);
    B.x[1][1]=po[t];
    B.x[2][1]=B.x[2][2]=B.x[3][1]=B.x[3][2]=B.x[3][3]=1;
    ksm(y-x+1);
}
int main()
{   
    scanf("%lld%lld",&n,&m);
    po[0]=1;
    for(int i=1;i<=19;i++) po[i]=po[i-1]*10%m;
    A.x[1][3]=1;
    long long t=1,sum=1;
    while(sum*10<=n) work(sum,sum*10-1,t),t++,sum*=10;
    work(sum,n,t);  
    printf("%lld",A.x[1][1]);
    return 0;
}