Description
有一个 $1$ 到 $n$ 的排列 $p_1,p_2,p_3,…,p_n$，你会对它进行若干轮操作，每一轮操作，你会保留序列中极大的数，也就是说对于每个数字，如果它比相邻的数字都大，那么会被保留下来。比如一个排列 $(3,2,5,1,4,6)$，经过一轮操作之后序列变成 $(3,5,6)$，第二轮操作之后序列变成 $(6)$，经过恰好 $2$ 轮之后序列里只有一个元素。
请问有多少个长度为 $n$ 的序列，经过恰好 $k$ 次操作之后，序列里只有一个元素，由于答案很大，对一个素数 $P$ 取模。
Idea
⾸先考虑给定⼀个排列，我们计算它⼏次会被消掉。
考虑这个排列的笛卡尔树，那么当⼀个数它的左⼦树或者右⼦树都被消掉的时候，它就会和它的祖先直接相邻，也就是⼀个⽐它⼤的数。
所以记 $dp[u]$ 表示笛卡尔树中 $u$ 这个点的⼦树什么时候被全部消完。那么有 $dp[u]=\max (dp[l],dp[r],\min (dp[l],dp[r])+1)$。
我们得到了⼀个 $\Theta(n)$ 的判断⼀个序列多少轮被消完的⽅法。
可以把这个 $dp$ 的过程直接改成计数。
令 $dp[u][k]$ 表示⼤⼩为 $u$ 的⼦树，能存活 $k$ 轮。$dp$ 的时候枚举最⼤值在哪⾥，分成左右两边计算。
因为最多存活 $\log n$ 轮，时间复杂度为 $\Theta(n^2\log ^2 n)$。
Code
#include <bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define maxn 1010
#define maxm 11
int f[maxn][maxm],g[maxn][maxm];
int c[maxn][maxn],n,m,p,ans;
void inc(int &x,int y){x+y>=p?x=x+y-p:x=x+y;}
int read(){
int x=0,flag=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if (ch=='-') ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
return x*flag;
}
int main(){
n=read(),m=read(),p=read();
for (int i=0;i<n;++i){
c[i][0]=1;
for (int j=1;j<=i;++j)
inc(c[i][j],c[i-1][j]+c[i-1][j-1]);
}
f[0][0]=g[0][0]=f[1][1]=g[1][1]=1;
for (int i=2;i<n;++i)
for (int k,r,j,l=0;l<i;++l){
r=i-l-1;k=c[i-1][l];
for (int x=0;x<=m;++x) if (f[l][x]){
for (int y=0;y<=m;++y) if (f[r][y]||g[r][y]){
j=(x==y?x+1:max(x,y));
inc(f[i][j],1ll*f[l][x]*f[r][y]%p*k%p);
j=max(x+1,y);
inc(g[i][j],1ll*f[l][x]*g[r][y]%p*k%p);
}
}
}
for (int k,r,l=0;l<n;++l){
r=n-l-1;k=c[n-1][l];
for (int x=0;x<m;++x) inc(ans,1ll*g[l][x]*g[r][m]%p*k%p);
for (int x=0;x<m;++x) inc(ans,1ll*g[l][m]*g[r][x]%p*k%p);
inc(ans,1ll*g[l][m]*g[r][m]%p*k%p);
}
printf("%d\n",ans);
return 0;
}