记录编号	151969	评测结果	AAAAAAAAAA
题目名称	[HNOI 2011] 数学作业	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-03-12 12:14:05	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

typedef long long int64;

using namespace std;

int64 N,M;

struct MA{
	int64 a[4][4];
	int n,m;
	void init(int x,int y){
		n=x; m=y;
		memset(a,0,sizeof(a));
	}
	MA operator*(const MA &x){
		MA re;
		re.init(n,x.m);
		for(int i=1;i<=re.n;i++)
			for(int j=1;j<=re.m;j++)
				for(int k=1;k<=m;k++)
					re.a[i][j]=(re.a[i][j]+a[i][k]*x.a[k][j]%M)%M;
		return re;
	}
	void print(){
		cout<<"Matrix : "<<n<<' '<<m<<endl;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
				cout<<a[i][j]<<' ';
			cout<<endl;
		}
	}
}Ans,A;

MA qpow(MA &x,int64 n){
	MA re,tp=x;
	re.init(3,3);
	for(int i=1;i<=3;i++) re.a[i][i]=1;
	for(;n>0;n>>=1,tp=tp*tp) if(n&1) re=re*tp;
	return re;
}

int main(){
	freopen("mathwork.in","r",stdin);
	freopen("mathwork.out","w",stdout);
	scanf("%lld%lld",&N,&M);
	int cnt=0;
	for(int64 tmp=N;tmp>0;tmp/=10) cnt++;
	int64 tmp=1;
	Ans.init(1,3);
	Ans.a[1][3]=1;
	A.init(3,3);
	A.a[2][1]=A.a[2][2]=A.a[3][2]=A.a[3][3]=1;
	for(int i=1;i<=cnt;i++,tmp=tmp*10LL){
		A.a[1][1]=(tmp*10LL)%M;
		Ans.a[1][2]=tmp%M;
		Ans=Ans*qpow(A,min(N,tmp*10LL-1LL)-tmp+1LL);
	}
	//Ans.print();
	printf("%lld\n",Ans.a[1][1]);
}