[bzoj2326] [洛谷P3216] [HNOI2011] 数学作业

---

想法##

最初的想法就是记录当前 \(%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;

}