题目描述

给定 \(n\), \(k\), \(m\) , 问有多少个序列组 \((A_0,A_1,…,A_n)\) 满足：序列 \(A_i\) 的元素个数为 \(i\) ; 所有元素都在 \([1,k]\) 内; \(\forall i\in[0,n)\) , \(A_i\) 是 \(A_{i+1}\) 的子序列且 \(A_i\) 的字典序小于 \(A_{i+1}\).

输出在 \(\bmod \ m\) 意义下的答案.

Solution

又抄题解去了/kk。
为什么这也可以上树啊/kk。
可以发现本质上我们干的事情就是计数一个操作序列， 每次往序列里面加入一个数， 满足后面一个序列的字典序大于前面那个序列。那么每次就是考虑往序列里面某个数的前面放数， 要求放的数\(x\)小于这个数。
但是这个东西直接\(dp\)并不好刻画， 考虑搞一棵操作树。这个树上的节点用一对数来刻画\((id, val)\)。如果我们建立虚节点\((0, 0)\)， 那么每次插入的时候就是选择一个\(val < x\)的位置， 在这个点下面挂一个点\((now, x)\)。那么这样构造出来的一棵树直接与原序列对应。直接考虑对树计数即可。
那么考虑设\(dp_{i, j}\)表示\(i\)个节点的树， 根节点权值为\(j\)的树的个数， 有转移：

\[dp_{i, j} = \sum_{p = 1}^{i - 1}\binom{i - 2}{p - 1}\times dp_{i - p, j}\times \sum_{q = j + 1}^kdp_{p, q} \]

意义就是枚举根节点\(id\)最小的子树的大小， 分配标号以后再枚举这个子树根节点权值， 前缀和优化以后显然可以\(O(n^2k)\)。