想法
最初的想法就是记录当前 \(%m\) 值为cur，到下一个数时 \(cur=cur \times 10^x + i\) n这么大，那就矩阵乘法呗。 矩阵乘法使用的要点就是有一个转移矩阵会不停的用到。 那么这道题中，1~n中所有位数相同的数转移矩阵都相同。\[ \begin{bmatrix} ans & i &1 \end{bmatrix} \begin{bmatrix} 10^x & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} ans' & i+1 & 1 \end{bmatrix} \]
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int SZ=6;
ll n,m;
struct matrix{
ll a[SZ][SZ];
matrix() { memset(a,0,sizeof(a)); }
void init() { for(int i=0;i<SZ;i++) a[i][i]=1; }
matrix operator * (const matrix &b) const{
matrix c;
for(int i=0;i<SZ;i++)
for(int j=0;j<SZ;j++)
for(int k=0;k<SZ;k++)
(c.a[i][j]+=a[i][k]*b.a[k][j])%=m;
return c;
}
matrix operator *= (const matrix &b) { return *this=*this*b; }
};
matrix Pow_mod(matrix x,ll y){
matrix ret; ret.init();
while(y){
if(y&1) ret*=x;
x*=x;
y>>=1;
}
return ret;
}
int main()
{
scanf("%lld%lld",&n,&m);
matrix a,b;
b.a[0][2]=1;
for(ll i=1;i<=n;i*=10){
a.a[1][0]=a.a[1][1]=a.a[2][0]=a.a[2][1]=a.a[2][2]=1;
a.a[0][0]=(i*10)%m;
a=Pow_mod(a,min(n-i+1,i*9));
b=b*a;
}
printf("%lld\n",b.a[0][0]);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8546544.html
