传送门
首先我们可以将计算出所有上升序列的答案，然后自由组合乘上个(n!)就行了
我们设(f(n))为长度为(n)的上升序列的答案,(f(n,x))为长度为(n)并且包含(x)的上升序列的答案
那么显然有
[f(n)=frac{1}{n}sum_{i=1}^{A}f(n,i)
]
也有
[f(n,x)=x(f(n-1)-f(n-1,x))\
x^if(n-i-1)=x^{i}f(n-i-1,x)+x^{i-1}f(n-i,x)\
x^if(n-i)=x^{i}f(n-i,x)+x^{i-1}f(n-i+1,x)\
]
我们可以考虑容斥
[f(n,x)=sum_{i=1}^{n}(-1)^{i+1}x^if(n-i)
]
然后我们就可以把这个式子直接套到第一个式子里
[f(n)=frac{1}{n}sum_{j=1}^{A}sum_{i=1}^{n}(-1)^{i+1}j^if(n-i)\
f(n)=frac{1}{n}sum_{i=1}^{n}(-1)^{i+1}sum_{j=1}^{A}j^if(n-i)\
]
然后对于((-1)^{i+1}sum_{j=1}^{A}j^i)就是自然数幂和
伯努利数或者拉格朗日插值都行的
时间复杂度(O(n^2))
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=510;
int n,m,mod,fac[maxn],facinv[maxn],B[maxn],inv[maxn],g[maxn],f[maxn];
int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}
int del(int x,int y){return x-y<0?x-y+mod:x-y;}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int mi(int a,int b){
int ans=1;while(b){if(b&1)ans=mul(ans,a);b>>=1,a=mul(a,a);}
return ans;
}
int C(int n,int m){return mul(fac[n],mul(facinv[m],facinv[n-m]));}
int main()
{
read(m),read(n),read(mod);
fac[0]=inv[0]=facinv[0]=B[0]=1;
for(rg int i=1;i<=n+1;i++)fac[i]=mul(fac[i-1],i),inv[i]=mi(i,mod-2);
facinv[n+1]=mi(fac[n+1],mod-2);
for(rg int i=n;i;i--)facinv[i]=mul(facinv[i+1],i+1);
for(rg int i=1;i<=n;i++){
for(rg int j=0;j<i;j++)B[i]=add(mul(C(i+1,j),B[j]),B[i]);
B[i]=del(mod,mul(B[i],inv[i+1]));
}
B[1]=add(B[1],1);
for(rg int i=1;i<=n;i++){
for(rg int j=0;j<=i;j++)g[i]=add(g[i],mul(C(i+1,j),mul(B[j],mi(m,i-j+1))));
if(i&1)g[i]=mul(g[i],inv[i+1]);
else g[i]=del(mod,mul(g[i],inv[i+1]));
}
f[0]=1;
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=i;j++)
f[i]=add(f[i],mul(f[i-j],g[j]));
f[i]=mul(inv[i],f[i]);
}
printf("%d
",mul(f[n],fac[n]));
}