记录编号	130785	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]calc	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.232 s
提交时间	2014-10-23 09:38:07	内存使用	4.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=510;
LL A,N,MOD;
LL fact[SIZEN],inv_fact[SIZEN];
LL m[SIZEN],rm[SIZEN];
//m[i]=A(A-1)...(A-i+1)
LL powA[SIZEN];
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		n>>=1;
		a=(a*a)%MOD;
	}
	return ans;
}
LL inverse(LL x){
	return quickpow(x,MOD-2);
}
void calc_dbl(LL A,LL a[SIZEN],LL b[SIZEN],LL c[SIZEN]){//A~2A
	m[0]=1;
	for(int i=1;i<=N;i++) m[i]=(m[i-1]*(A-i+1))%MOD;
	for(int i=0;i<=N;i++) rm[i]=inverse(m[i]);
	powA[0]=1;
	for(int i=1;i<=N;i++) powA[i]=(powA[i-1]*A)%MOD;
	for(int i=0;i<=N;i++){//b[i]=在后一半选i个
		b[i]=0;
		for(int j=0;j<=i;j++){
			LL tmp=m[i];
			tmp=(tmp*powA[i-j])%MOD;
			tmp=(tmp*a[j])%MOD;
			tmp=(tmp*rm[j])%MOD;
			tmp=(tmp*inv_fact[i-j])%MOD;
			b[i]=(b[i]+tmp)%MOD;
		}
	}
	for(int i=0;i<=N;i++) c[i]=0;
	for(int i=0;i<=N;i++){
		for(int j=0;j<=i;j++) c[i]=(c[i]+a[j]*b[i-j])%MOD;
	}
}
void calc_pls(LL A,LL a[SIZEN],LL b[SIZEN]){//A~A+1
	for(int i=0;i<=N;i++){
		b[i]=a[i];
		if(i>0) b[i]=(b[i]+(A+1)*a[i-1])%MOD;
	}
}
int lg2(LL x){
	int ans=0;
	while(x>1) ans++,x>>=1;
	return ans;
}
LL f[2*SIZEN][SIZEN];
LL atp[SIZEN];
void work(void){
	int k=lg2(A);
	for(int i=0;i<=N;i++) f[1][i]=0;
	f[1][1]=1;f[1][0]=1;
	int tot=1;
	LL nowa=1;
	for(int i=k-1;i>=0;i--){
		calc_dbl(nowa,f[tot],atp,f[tot+1]);
		nowa<<=1;tot++;
		if((A>>i)&1){
			calc_pls(nowa,f[tot],f[tot+1]);
			nowa++;tot++;
		}
	}
	LL ans=f[tot][N];
	ans=(ans*fact[N])%MOD;
	printf("%lld\n",ans);
}
void prepare(void){
	fact[0]=1;
	for(int i=1;i<=N;i++) fact[i]=(fact[i-1]*i)%MOD;
	for(int i=0;i<=N;i++) inv_fact[i]=inverse(fact[i]);
}
int main(){
	freopen("nt2012_clj_calc.in","r",stdin);
	freopen("nt2012_clj_calc.out","w",stdout);
	scanf("%lld%lld%lld",&A,&N,&MOD);
	prepare();
	work();
	return 0;
}