记录编号	117624	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] 数学作业	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2014-08-30 18:51:14	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL N,M;
class MATRIX{
public:
	int n,m;
	LL s[3][3];
	void clear(int x,int y){
		n=x,m=y;
		memset(s,0,sizeof(s));
	}
	void print(void){
		printf("size: %d %d\n",n,m);
		for(int i=0;i<n;i++){for(int j=0;j<m;j++){printf("%d ",s[i][j]);}printf("\n");}
	}
};
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX c;
	c.clear(a.n,b.m);
	for(int i=0;i<c.n;i++)
		for(int j=0;j<c.m;j++)
			for(int k=0;k<a.m;k++)
				c.s[i][j]=(c.s[i][j]+a.s[i][k]*b.s[k][j])%M;
	return c;
}
MATRIX quickpow(MATRIX a,LL n){
	MATRIX ans;
	ans.clear(a.n,a.n);
	for(int i=0;i<a.n;i++) ans.s[i][i]=1;//单位矩阵
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;n>>=1;
	}
	return ans;
}
int countlen(LL n){
	int ans=0;
	while(n) n/=10,ans++;
	return ans;
}
void work(void){
	int len=countlen(N);
	LL ind=1,temp;
	MATRIX O;
	O.clear(1,3);
	O.s[0][2]=1;
	MATRIX D;
	D.clear(3,3);
	D.s[1][0]=D.s[1][1]=D.s[2][1]=D.s[2][2]=1;
	for(int i=1;i<=len;i++){
		D.s[0][0]=(ind*10)%M;
		O.s[0][1]=ind%M;
		temp=min(N,ind*10-1)-ind+1;
		O=O*quickpow(D,temp);
		ind*=10;
	}
	cout<<O.s[0][0]<<endl;
}
int main(){
	freopen("mathwork.in","r",stdin);
	freopen("mathwork.out","w",stdout);
	cin>>N>>M;
	work();
	return 0;
}