记录编号	336761	评测结果	AAAAAAAAWW
题目名称	[HZOI 2016]定约servant	最终得分	80
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	4.067 s
提交时间	2016-11-03 17:53:57	内存使用	76.58 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=10000000;
LL phi;
struct MA{
	LL a[3][3];
	MA(){memset(a,0,sizeof(a));}
	void init(LL k){for(int i=1;i<=2;i++)a[i][i]=k;}
	MA operator*(const MA &b)const{
		MA c;
		for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)
			c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%phi)%phi;
		return c;
	}
	LL *operator[](int x){return a[x];}
}A,B;
LL Lucas(int,int);
LL C(int,int);
LL inv(LL,LL);
LL qpow(LL,LL,LL);
LL euler_phi(LL);
MA qpow(MA,LL);
int gcd(int,int);
int n,m,p;
LL f[maxn],a=0,b=0;
int main(){
#define MINE
#ifdef MINE
	freopen("servant.in","r",stdin);
	freopen("servant.out","w",stdout);
#endif
	scanf("%d%d%d",&n,&m,&p);
	phi=euler_phi(p);
	f[0]=1;
	for(int i=1;i<=n&&i<=p;i++)f[i]=f[i-1]*i%p;
	A[1][2]=1;
	B[1][1]=B[1][2]=B[2][1]=1;
	A=A*qpow(B,n);
	a=A[1][1]%phi;
	A=A*B;
	a=a*A[1][1]%phi;
	for(int i=1;i<=m+1;i++)if(gcd(i,m)==1)b=(b+Lucas(n,i-1))%p;
	printf("%d",(int)qpow(b,a+phi,p));
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
LL Lucas(int n,int m){
	if(!m)return 1ll;
	if(!n)return 0ll;
	return Lucas(n/p,m/p)*C(n%p,m%p)%p;
}
LL C(int n,int m){
	if(n<m)return 0ll;
	return f[n]*inv(f[m]*f[n-m]%p,p)%p;
}
LL inv(LL a,LL p){
	return qpow(a,phi-1,p);
}
LL qpow(LL a,LL b,LL p){
	LL ans=1ll;
	for(;b;b>>=1,a=a*a%p)if(b&1ll)ans=ans*a%p;
	return ans;
}
LL euler_phi(LL n){
	LL ans=n;
	int m=(int)ceil(sqrt(n));
	for(int i=2;n>1&&i<=m;i++)if(n%i==0){
		ans=ans/i*(i-1);
		do n/=i;while(n%i==0);
	}
	if(n>1)ans=ans/n*(n-1);
	return ans;
}
MA qpow(MA a,LL b){
	MA ans;
	ans.init(1);
	for(;b;b>>=1,a=a*a)if(b&1ll)ans=ans*a;
	return ans;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
/*
降幂大法：
a^b = a^(b%phi(p)+phi(p))(b>=phi(p))
*/