Description：

计算 $1,2,\dots,N$ 顺序连接起来的数 $\%m$ 的值。

$1\le n \le 10^{18}$

Solution：

$10^{18}$ 的数据范围差不多就是矩阵快速幂了，转移方程为 $f[i]=f[i-1]\times 10^{\lfloor\lg i\rfloor}+i(\text{mod }m)$ ，枚举 $\lfloor \lg i\rfloor$ 构造矩阵即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n,p;

struct matrix

{

    ll m[4][4];

    matrix(){memset(m,0,sizeof(m));}

    friend matrix operator * (matrix a,matrix b)

    {

        matrix c;

        for(int i = 1;i <= 3;++i)

            for(int j = 1;j <= 3;++j)

                for(int k = 1;k <= 3;++k)

                    c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % p) % p;

        return c;

    }

    friend matrix operator ^ (matrix a,ll b)

    {

        matrix res = a;--b;

        while(b > 0)

        {

            if(b & 1)res = res * a;

            a = a * a;

            b = b >> 1;

        }

        return res;

    }

}f,res;

int main()

{

    scanf("%lld%lld",&n,&p);

    res.m[1][1] = res.m[1][2] = res.m[1][3] = 1;

    f.m[1][1] = 10;

    f.m[2][1] = f.m[3][1] = f.m[2][2] = f.m[3][2] = f.m[3][3] = 1;

    if(n <= 9)

    {

        for(int b = 2;b <= n;++b)

        {

            res = res * f;

        }

        cout << res.m[1][1] << endl;

        return 0;

    }

    else res = res * (f ^ 8);

    for(ll b = 2,cur = 100;b <= 18;++b,cur *= 10)

    {

        f.m[1][1] = cur % p;

        f.m[2][1] = f.m[3][1] = f.m[2][2] = f.m[3][2] = f.m[3][3] = 1;

        if(n < cur)

        {

            res = res * (f ^ (n - cur / 10 + 1));

            break;

        }

        else

        {

            res = res * (f ^ (cur / 10 * 9));

        }

    }

    cout << res.m[1][1] << endl;

    return 0;

}