拉格朗日插值+dp
直接dp是n立方的，我们考虑优化。
dp式子为f[i][j]=f[i-1][j-1]*j*i+f[i-1][j]表示i个元素选j个的答案
然后发现最高次就是2j次，所以我们预处理出2n个点的值再用拉格朗日一插就好。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int A,n,mod; 5 int qmod(int a,int b) 6 { 7 int ans=1; 8 while(b) 9 { 10 if(b&1)ans=1ll*ans*a%mod; 11 b>>=1;a=1ll*a*a%mod; 12 } 13 return ans; 14 } 15 ll f[1005][505],inv[1005],las[1005],fac[1005],pre[1005],ans; 16 int main() 17 { 18 scanf("%d%d%d",&A,&n,&mod); 19 f[0][0]=1; 20 for(int i=1;i<=min(n*2,A);++i) 21 for(int j=0;j<=n;++j) 22 if(j)f[i][j]=(1ll*i%mod*j%mod*f[i-1][j-1]%mod+f[i-1][j])%mod; 23 else f[i][j]=f[i-1][j]; 24 if(A<=n*2){ 25 printf("%d ",f[A][n]); 26 return 0; 27 } 28 inv[1]=inv[0]=fac[0]=inv[0]=1; 29 pre[0]=A%mod; 30 for(int i=1;i<=n*2;++i) 31 { 32 pre[i]=pre[i-1]*(A-i)%mod; 33 fac[i]=fac[i-1]*i%mod; 34 } 35 las[n*2]=(A-n*2)%mod;inv[n*2]=qmod(fac[n*2],mod-2); 36 for(int i=n*2-1;i>=0;--i)las[i]=las[i+1]*(A-i+mod)%mod; 37 for(int i=n*2-1;i>=1;--i)inv[i]=inv[i+1]*(i+1)%mod; 38 for(int i=0;i<=n*2;++i) 39 { 40 ll INV,FAC=1; 41 if((n*2-i)&1)INV=-1ll*inv[i]*inv[n*2-i]%mod; 42 else INV=1ll*inv[i]*inv[n*2-i]%mod; 43 if(i>0)FAC=pre[i-1]%mod; 44 if(i<n*2)FAC=FAC*las[i+1]%mod; 45 ans=(ans+FAC*f[i][n]%mod*INV%mod)%mod; 46 } 47 printf("%lld ",(ans+mod)%mod); 48 return 0; 49 }