Link.
Description.
给定 \(n,k,m\)，统计序列序列数 \(\{A_i(i\in[0,n])\}\)，使得
- \(\text{size}(A_i)=i\)
- \(\forall i\in[1,n],j\in[1,i],A_i(j)\in[1,k]\)
- \(\forall i\in[1,n]\)，\(A_{i-1}\) 是 \(A_i\) 的子序列且字典序小于 \(A_i\)
Solution.
自己的想法：
题意转化成了求不同操作序列数
- 每次末尾插入一个任意元素
- 每次在第 \(k\) 个位置插入一个权值 \(>a_k\) 的元素
题解：
发现在开头插个 \(0\)，上面的 \(1\) 就和 \(2\) 合并了，两者是本质相同的。
然后考虑建树，一个点向它插入位置连边，还要记录一个当前是第几次操作。
本质上来说，一个点当前第几次操作其实在树的形态确定时是基本确定的。
只能在所有儿子改变顺序时才能变。
那我们考虑记录 \(dp_{x,y}\) 表示大小为 \(x\) 根权为 \(y\) 的子树的方案数。
我们枚举第一个子树是什么，然后删掉后 \(dp\) 状态是已知的。
枚举第一个子树的大小和根权，则有
Coding.
点击查看代码
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
int n,K,P,dp[305][305],sm[305][305],C[305][305];
inline void upd(int &a,int b) {(a+=b)>=P?a-=P:a;}
int main()
{
read(n,K,P);for(int i=K;i>=0;i--) sm[1][i]=sm[1][i+1]+(dp[1][i]=1);
for(int i=0;i<=n;i++) {C[i][0]=1;for(int j=1;j<=i;j++) upd(C[i][j]=C[i-1][j-1],C[i-1][j]);}
for(int i=2;i<=n+1;i++) for(int j=K;j>=0;upd(sm[i][j]=sm[i][j+1],dp[i][j]),j--)
for(int l=1;l<i;l++) upd(dp[i][j],1ll*C[i-2][l-1]*dp[i-l][j]%P*sm[l][j+1]%P);
return printf("%d\n",dp[n+1][0]),0;
}