Sequence Growing Hard
不难发现设合法的条件为第 k 位后,需满足 \(k\in[1,n)\)\(A_{i,k+1}\leq A_{i+1,k}\) 或 k=n。
对于连续相等的一段,在任意位置放得到的 A_{i+1} 相同需去重。
以上两种方式体现为,在末尾放 x,放一段不降序列,再在末尾放 x,再放一段不降序列。以此类推。
所以我们把在末尾放 x 作为特殊操作,思考如何表示放不降序列的过程。
发现使用树形 DP,\(dp_{i,j}\) 表示点数为 i,根节点权值为 j,子节点权值>=j 的方案数。
题目变为有标号树个数计数。
特别的,i 连向根节点表示放入 i 序列末尾。
由于需要去重,需要钦定一个编号最小的节点放在前面,具体的
\[dp_{i,j}=\sum_{k=1}^{i-1}\sum_{l=j+1}^{up}\binom{i-2}{k-1}dp_{k,l}dp_{i-k,j}
\]
意思就是新加入 k-1 个点后把这些点是第几个放入插板。
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
const int MAXN=305;
int n,m,Mod;
ll dp[MAXN][MAXN],s[MAXN][MAXN],c[MAXN][MAXN];
int main(){
scanf("%d%d%d",&n,&m,&Mod);
c[0][0]=1;
for(int i=1;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=i;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%Mod;
}
}
for(int i=0;i<=m;i++){
dp[1][i]=1;s[1][i]=m-i+1;
}
for(int i=2;i<=n+1;i++){
for(int k=m;k>=0;k--){
for(int j=1;j<i;j++){
dp[i][k]=(dp[i][k]+c[i-2][j-1]*(s[j][k+1]*dp[i-j][k]%Mod)%Mod)%Mod;
}
s[i][k]=(dp[i][k]+s[i][k+1])%Mod;
}
}
printf("%lld",dp[n+1][0]);
return 0;
}