(日常聊天)表示蒟蒻的我,并不太记得住矩阵是怎样乘的,但我记住了代码,所以有没有哪位大佬教一下我矩阵乘法,万分感谢。
明天又可以来机房啦,好开心,最近在学数位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; }