记录编号	439653	评测结果	AAAAAAAAAA
题目名称	五彩的色子	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2017-08-21 11:50:28	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{   char c=getchar();int x=0,y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
typedef long long ll;
int ki;
ll n,m;
struct matrix
{	ll s[5][5];
	void cl(){mem(s,0);}
	matrix(){cl();}
	void init(){cl();for(int i=0;i<2;i++) s[i][i]=1;}
	friend matrix operator * (matrix x,matrix y)
	{	matrix z;ll tmp;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
				{	tmp=(x.s[i][k]*y.s[k][j])%ki;
					z.s[i][j]=(z.s[i][j]+tmp)%ki;
				}
		return z;
	}
}A,ans;
int main()
{   freopen("colorful.in","r",stdin);
	freopen("colorful.out","w",stdout);
	scanf("%lld%lld%d",&n,&m,&ki);
	if(n==1){printf("%lld",(m-1)%ki);return 0;}
	A.s[0][0]=(m-1)%ki;A.s[0][1]=1;A.s[1][0]=1;A.s[1][1]=(m-1)%ki;
	ans.init();
	ll edg=n-1;
	for(;edg;edg>>=1,A=A*A)
		if(edg&1) ans=ans*A;
	printf("%lld",((ans.s[0][0]*((m-1)%ki))%ki+ans.s[0][1])%ki);
	return 0;
}