题目大意

将$[1,n]$这$n$个数连在一起，然后求这个大数字除以$m$的余数

数据范围

$1\leqslant n\leqslant 10^{18},1\leqslant m\leqslant 10^9$

题解

f(i)表示[1,i]这i个数连在一起的大数字，可以设计一个矩阵来递推$f(1)-f(n)$ $$ \left[ \begin{matrix} f(i-1) & i-1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} \right] \times \left[ \begin{matrix} 10^t & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ \end{matrix} \right] = \left[ \begin{matrix} f(i) & i & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} \right] $$

得到矩阵乘法递推式之后，发现递推式中数字的位数$(t)$会发生改变，即需要按照数字的位数分段递推

可以先用快速幂算出一段中的矩阵乘积，其中$k$是这一段中数字的个数(即需要递推的次数)，形式上来说就是 $$ \left[ \begin{matrix} f(i-k) & i-1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} \right] \times \left[ \begin{matrix} 10^t & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} \right]^k = \left[ \begin{matrix} f(i) & i & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{matrix} \right] $$

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=(ll)x*10+ch-48;ch=getchar();}
    return (ll)x*f;
}

ll n,m,t=10;
ll a[4][4],ans[4][4];
inline void mul(ll a[4][4],ll b[4][4],ll result[4][4]){
    ll c[4][4];memset(c,0,sizeof(c));
    For(i,1,3) For(j,1,3)
        For(p,1,3) c[i][j]=(c[i][j]+(a[i][p]%m)*(b[p][j]%m))%m;
    For(i,1,3) For(j,1,3) result[i][j]=c[i][j];
}

inline void count(ll t,ll last){
    memset(a,0,sizeof(a));
    a[1][1]=t;a[2][1]=a[2][2]=a[3][1]=a[3][2]=a[3][3]=1;
    ll k=last-t/10+1;
    while (k){
        if (k&1) mul(ans,a,ans);
        k>>=1;mul(a,a,a);
    }
}
int main(){
    n=read(),m=read();ans[1][3]=1;
    while (n>=t){count(t,t-1);t*=10;}
    count(t,n);
    printf("%lld\n",ans[1][1]);
    return 0;
}