P3216 [HNOI2011] 数学作业 矩阵 40分WA #4~#10

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll n,m,pt;
struct node
{
	ll n,m,x[5][5];
}a,b,ans;
node ji(node u,node o)
{
	node res;
	memset(res.x,0,sizeof(res.x));
	for(ll i=1;i<=u.n;i++)
	{
		for(ll j=1;j<=o.m;j++)
		{
			for(ll l=1;l<=u.m;l++)
			{
				res.x[i][j]=((res.x[i][j]+(u.x[i][l]*o.x[l][j]+m)%m)+m)%m;
			}
		}
	}
	res.n=u.n;
	res.m=o.m;
	return res;
}
node p(node num,ll go){
	go--;
	node res=num;
	while(go){
		if(go&1){
			res=ji(res,num);
		}
		num=ji(num,num);
		go>>=1;
	}
	return res;
}
int main()
{
	cin>>n>>m;
	memset(a.x,0,sizeof(a.x));
	memset(b.x,0,sizeof(b.x));
	a.n=a.m=b.m=b.n=3;
	a.x[1][3]=1;
	pt=10;
	b.x[2][1]=b.x[2][2]=b.x[3][1]=b.x[3][2]=b.x[3][3]=1;
	if(n==0){
		cout<<0;
		return 0;
	}
	while(pt<=n){
		b.x[1][1]=pt;
		a=ji(a,p(b,pt-pt/10));
		pt*=10;
	}
	b.x[1][1]=pt;
	ans=ji(a,p(b,n-pt/10+1));
	cout<<ans.x[1][1];
}