巧妙地转换为数树的问题，但也可以从序列角度理解。
视作每次加入一个数，要求序列字典序单调递增。考虑合法的充要条件，我们先在末尾插入一个 $0$ 将插在末尾转化为下面的情况，设插入的数为 $x$，容易发现需满足二者之一：1.$v$ 为 $x$ 的下一个数，满足 $x<v$；2.$v$ 为 $x$ 之后不与 $x$ 相等的第一个数，满足 $x<v$。但二者只需条件 1 即可，因为满足条件 2 的序列必然与某一个满足条件 1 的序列重复（将 $x$ 插在与 $x$ 相等的段的末尾即可得到一个满足条件 1 的序列），这样就直接去重了。
考虑转化，每次操作从 $x$ 向 $v$ 连边，那么我们可以得到一颗树，二者构成双射。其中父亲权值大于儿子权值。设 $f(v,s)$ 为当根节点权值为 $v$，子树大小为 $s$ 时的方案数。转移每次考虑在左边插入一个子树，得到：
如何从序列角度理解？相当于按照真正的操作顺序从后往前，钦定序列的末尾，转移相当于每次加入一个之前的操作。
时间复杂度 $\mathcal O(n^2m)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=300+10;
int n,m,mod;
int C[N][N],f[N][N],sum[N][N];
inline int adj(int x){return x>=mod?x-mod:x;}
int main()
{
scanf("%d %d %d",&n,&m,&mod);
n++;
for(int i=0;i<=n;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=adj(C[i-1][j]+C[i-1][j-1]);
}
for(int i=m;~i;i--)sum[i][1]=sum[i+1][1]+(f[i][1]=1);
for(int i=m;~i;i--)
for(int j=1;j<=n;sum[i][j]=adj(sum[i+1][j]+f[i][j]),j++)
for(int k=1;k<=j-1;k++)
f[i][j]=adj(f[i][j]+1ll*f[i][j-k]*C[j-2][k-1]%mod*sum[i+1][k]%mod);
printf("%d",f[0][n]);
return 0;
}
|