bzoj2326: [HNOI2011]数学作业

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define ll long long
ll a[4][4],b[4][4],n,mod;
void mul(ll a[4][4],ll b[4][4],ll ans[4][4]){
	ll tmp[4][4];clr(tmp,0);
	rep(i,3) rep(j,3) rep(k,3) tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
	rep(i,3) rep(j,3) ans[i][j]=tmp[i][j];
}
void cal(ll t,ll cnt){
	clr(b,0);b[1][1]=t%mod,b[2][1]=b[2][2]=b[3][1]=b[3][2]=b[3][3]=1;
	ll y=cnt-t/10+1;
	while(y){
		if(y&1) mul(a,b,a);
		mul(b,b,b);y>>=1;
	}
}
int main(){
	scanf("%lld%lld",&n,&mod);
	clr(a,0);a[3][3]=1;
	ll t=10;
	while(n>=t) cal(t,t-1),t*=10;
	cal(t,n);printf("%lld\n",a[3][1]);
	return 0;
}