记录编号	406275	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]calc	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.466 s
提交时间	2017-05-18 11:16:22	内存使用	5.45 MiB

#include<cstdio>
typedef long long ll;
const int N=1010;
int n,m,mod,dp[N][N],inv[N];
int inc(int x,int y){x+=y;return x>=mod?x-mod:x;}
int dec(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
//猜测答案是个O(n)次多项式，于是拉格朗日插值…… 
int pre[N],suc[N];
int main()
{
	freopen("nt2012_clj_calc.in","r",stdin);
	freopen("nt2012_clj_calc.out","w",stdout);
	scanf("%d%d%d",&m,&n,&mod);
	inv[0]=inv[1]=1;
	for (int i=2;i<N;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
	for (int i=1;i<N;i++) inv[i]=mul(inv[i-1],inv[i]);
	for (int i=0;i<N;i++){
		dp[i][0]=1;
		for (int j=1;j<=i;j++) dp[i][j]=inc(mul(mul(i,j),dp[i-1][j-1]),dp[i-1][j]);
	}
	if (m<N) return printf("%d\n",dp[m][n]),0;
	int ans=0;
	for (int i=1;i<N;i++){
		int val=mul(mul(dp[i][n],inv[i-1]),mul(inv[N-i-1],power(m-i,mod-2)));
		if ((N-i)&1) ans=inc(ans,val);else ans=dec(ans,val);
	}
	for (int i=1;i<N;i++) ans=mul(ans,m-i);
	printf("%d\n",ans);
	return 0;
}