XXIX.[集训队互测2012] calc
考虑DP。
我们设\(f(i,j)\)表示所有有\(i\)个数，且每个数都处于\([1,j]\)区间内的递增序列的值之和。则答案即为\(f(n,m)\times n!\)（因为题目中不限制只有递增序列）
我们考虑DP，则有
\[f(i,j)=f(i-1,j-1)\times j+f(i,j-1)
\]
显然这玩意复杂度过高，无法求出。
但是我们根据直觉，每个\(f_i\)应是一个多项式，所以可以考虑拉格朗日插值。
那么这到底是一个几次多项式呢？我们设\(f(i)\)的次数是\(g(i)\)
则由上式，有
\[f(i)-f(i-1)=j\times f(i-1,j-1)
\]
即
\[g(i)-1=g(i-1)+1
\]
又有\(g(0)=0\)
所以我们最终可以得到\(g(i)=2i\)
然后我们只需要\(g(n)+1\)即\(2n+1\)个点即可插出\(f(n)\)出来；选择\(1\sim 2n+1\)即可。
时间复杂度\(O(n^2)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,mod,f[510][1010],res,FAC=1;
int ksm(int x,int y){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
return z;
}
int main(){
scanf("%d%d%d",&m,&n,&mod);
for(int j=0;j<=2*n+1;j++)f[0][j]=1;
for(int i=1;i<=n;i++)for(int j=1;j<=2*n+1;j++)f[i][j]=(1ll*f[i-1][j-1]*j%mod+f[i][j-1])%mod;
for(int i=1;i<=n;i++)FAC=1ll*FAC*i%mod;
// if(m<=2*n){printf("%d\n",1ll*f[n][m]*FAC%mod);return 0;}
for(int i=1;i<=2*n+1;i++){
int now=1;
for(int j=1;j<=2*n+1;j++)if(i!=j)now=1ll*now*(m-j+mod)%mod*ksm((i-j+mod)%mod,mod-2)%mod;
(res+=1ll*now*f[n][i]%mod)%=mod;
}
printf("%d\n",1ll*res*FAC%mod);
return 0;
}