（日常聊天）表示蒟蒻的我，并不太记得住矩阵是怎样乘的，但我记住了代码，所以有没有哪位大佬教一下我矩阵乘法，万分感谢。

明天又可以来机房啦，好开心，最近在学数位DP，有没有大佬教下我，谢谢！！！

首先，看题，我们会发现他有一个神奇的数据范围，然后我们往一个神奇的方向想，忽然，想到了（点开标签）矩阵乘法。

然后开始，我们的推式子之旅。

原始矩阵

首先，我们构建原始矩阵，先将我们的要求的数fn放入矩阵中，然后，再将题里所给信息，将n这个数放入矩阵中，如果这时，我们开始构建转移方程，我们会发现，在下一个矩阵中出不来n+1这个数，所以，我们再将一个常数1放入原始矩阵中。这样原始矩阵就构造好了。

转移矩阵

之后我们想如何将fn变为f（n+1），很容易想到，将f（n） * n这个数的位数，再加上n，

第一层，即是（ ,1,0）;

之后我们想如何将n变为n+1，这个也很容易想到，即借用一下那个常数1；

第二层，即是（0,1,1）；

第三层，不再废话，即是（0,0,1）；

最后即是!

请将第一行最后一个一变为0.

然后，用矩阵快速幂优化一下。

好的，下面上代码。

#include<bits/stdc++.h>

#define int long long

using namespace std;

struct node{
    int num[5][5],x,y;
}ma;

int n,num,cnt,m;

node ans;

node mul(node a,node b)
{
    node anss;

    memset(anss.num,0,sizeof(anss.num));

    anss.x=a.x;

    anss.y=b.y;

    for(int i=1;i<=a.y;i++)
    {
        for(int j=1;j<=a.x;j++)
        {
            for(int k=1;k<=b.y;k++)
            {
                anss.num[j][k]=(anss.num[j][k]+(a.num[j][i]*b.num[i][k])%m)%m;
            }
        }
    }

    return anss;
}

signed main()
{
    cin>>n>>m;

    int nn=n;

    while(nn!=0)
    {
        cnt++;

        nn=nn/10;
    }

    int num=1;

    ans.num[2][1]=1;

    ans.num[3][1]=1;

    ans.x=3; ans.y=1;

    ma.x=ma.y=3;

    for(int i=1;i<=cnt;i++)
    {
        memset(ma.num,0,sizeof(ma.num));

        num=num*10;

        ma.num[1][1]=num%m;

        ma.num[1][2]=ma.num[2][2]=ma.num[2][3]=ma.num[3][3]=1;

        int numm=num-num/10;

        if(i==cnt) numm=n-num/10+1;

        while(numm!=0)
        {
            if(numm%2==1) ans=mul(ma,ans);

            ma=mul(ma,ma);

            numm/=2;
        }

    }

    cout<<ans.num[1][1]%m<<'\n';

    return 0;

}

请不要吐槽代码码风，我的码风我做主。