C++14(g++5.4) 解法, 执行用时: 1237ms, 内存消耗: 165676K, 提交时间: 2020-08-01 18:47:31

#include<bits/stdc++.h>
using namespace std;
typedef long long L;
const int N=5011;
int p,n=5000;
int c[N][N],d[N][N],g[N],t[N],f[N],h[N];
//int Pow(int a,int b){int r=1;for(;b;b>>=1,a=(L)a*a%p)if(b&1)r=(L)r*a%p;return r;}
int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
#endif
	int T;
	cin>>T>>p;
	int i,j,x,y,z,u,v,w;
	for(i=0;i<=n;++i){
		c[i][0]=c[i][i]=1;
		for(j=1;j<i;++j)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
	}
	for(i=0;i<=n;++i){
		d[i][0]=1;
		for(j=1;j<=n;++j)
			d[i][j]=(L)d[i][j-1]*i%p;
	}
	for(i=2;i<=n;++i){
		for(j=0;j<=i-2;++j){
			g[i]=(g[i]+(L)c[i-2][j]*(j+1)*(j+1)%p*d[i-1][i-2-j])%p;
		}
		g[i]=(L)g[i]*i%p;
	}
	//cerr<<n<<" "<<g[2]<<" "<<g[3]<<" "<<g[4]<<endl;
	t[0]=t[1]=1;
	for(i=2;i<=n;++i)t[i]=d[i][i-2];
	h[0]=1;
	for(i=1;i<=n;++i){
		for(j=1;j<=i;++j){
			h[i]=(h[i]+(L)h[i-j]*t[j]%p*c[i-1][j-1])%p;
			f[i]=(f[i]+((L)f[i-j]*t[j]+(L)h[i-j]*g[j])%p*c[i-1][j-1])%p;
		}
	}
	while(T--){
		cin>>n;
		cout<<f[n]<<"\n";
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 3008ms, 内存消耗: 196984K, 提交时间: 2020-08-02 14:09:10

#include <cstdio>
const int N=5010;
int T,M,n,ans[N],dp[N],f[N],C[N][N],k[N][N];
int main(){
	scanf("%d%d",&T,&M);
	C[0][0]=dp[0]=dp[1]=1;
	register int i,j;
	for(i=1;i<N;++i){C[i][0]=k[i][0]=1;for(j=1;j<N;++j)C[i][j]=(C[i-1][j]%M+C[i-1][j-1]%M)%M,k[i][j]=1ll*k[i][j-1]*i%M;}
	for(i=2;i<N;++i)
		for(j=1;j<=i;++j) 
			dp[i]=(dp[i]+1ll*dp[i-j]%M*k[j][j-2<0?0:j-2]%M*C[i-1][j-1]%M)%M;
	for(i=1;i<N;++i)
		{for(j=1;j<i;++j)
			f[i]=(f[i]+1ll*j*j%M*C[i-2][j-1]%M*k[i-1][i-1-j]%M)%M;f[i]=1ll*f[i]*i%M;}
	for(i=2;i<N;++i)
		for(j=1;j<=i;++j)
			ans[i]=(ans[i]+1ll*C[i-1][j-1]%M*(1ll*k[j][j-2<0?0:j-2]*ans[i-j]%M+1ll*f[j]*dp[i-j]%M)%M)%M;
	while(T--)scanf("%d",&n),printf("%d\n",ans[n]);		
}