求满足以下条件的序列集合 { A 0 , A 1 , . . . , A N } \{A_0,A_1,...,A_N\} {A0,A1,...,AN} 的个数，模 M M M：
A i A_i Ai 长度为 i i i，其中每个元素都是 [ 1 , K ] [1,K] [1,K] 内的一个正整数。对于 i ≥ 1 i \geq 1 i≥1， A i A_i Ai 是由 A i − 1 A_{i-1} Ai−1 在某个位置插入一个数得到的。对于 i ≥ 1 i \geq 1 i≥1， A i A_i Ai 字典序大于 A i − 1 A_{i-1} Ai−1N , K ≤ 300 , M ≤ 1 0 9 N,K \leq 300,~M \leq 10^9 N,K≤300, M≤109
假设现在有了一个最终的序列 A N A_N AN，考虑有多少种生成到它的序列集合。 相当于每次删掉一个数。由于删掉之后字典序要变小，所以对于删的数，要么它右边比它小，要么它右边跟它相等，且一路过去最终比它小，但是为了避免计重，相等的这种情况不用理会。也就是说，对于单调不降的子段，它必须从后往前删。因此，如果把这个最终序列 A N A_N AN 分解成若干个单调不降的极长子段，每段长 l e n i len_i leni，那么它的方案数就是 N ! ∏ l e n i ! \frac{N!}{\prod len_i !} ∏leni!N!
这样就可以 dp 这个 A N A_N AN 了。设 f i , j f_{i,j} fi,j 表示长度为 i i i 的序列，最后一个元素为 j j j，的方案数。转移就是枚举最后一个极长子段，长度为 l e n len len，因此转移为 f i , j = ∑ l e n = 1 N ∑ j ′ = 2 k + 1 f i − l e n , j ′ ⋅ G l e n , j ′ − 1 , j l e n ! f_{i,j}=\sum_{len=1}^N \sum_{j'=2}^{k+1} f_{i-len,j'} \cdot \frac{G_{len,j'-1,j}}{len!} fi,j=len=1∑Nj′=2∑k+1fi−len,j′⋅len!Glen,j′−1,j
G l e n , s , t G_{len,s,t} Glen,s,t 是指长度为 l e n len len，开头小于等于 s s s，结尾为 t t t 的单调不降的序列个数，这个就是个挡板，可以预处理。这个各种优化之后就是 O ( n 2 k ) O(n^2k) O(n2k) 的啦！
一切就绪，编辑器，启动！
。。。 。。。 （一段时间之后。。。
woc 模数是他给的，不是质数就没有逆元了？？？？？
所以要搞个不用除法的 dp。。。
此处搬一下题解。 就考虑给一个序列插入一个数，同理，它只能插在一个比它小的数的左边。为了方便，假设一开始序列不为空，而是一个 0 0 0。 假设把 x x x 插在 y y y 左边，那么就在树上把 y y y 设为 x x x 的父亲。 设 i d x id_x idx 表示 x x x 这个节点是第几个插入的， v x v_x vx 表示它的值。那么这棵树满足儿子的 i d id id 和 v v v 都比父亲大。 不同的树与不同的序列集合一一对应，因此就是要求有多少棵树，使得任意儿子的两个权值都比父亲大。 设 f i , j f_{i,j} fi,j 表示这棵树大小为 i i i，点的 i d id id 为 1 1 1~ i i i，根节点的 v v v 值为 j j j，的方案数。显然 i d = 1 id=1 id=1 的点一定是根节点，它一定有一个儿子是 i d = 2 id=2 id=2，因此转移就是枚举 i d = 2 id=2 id=2 的这棵子树： f i , j = ∑ s i z e = 1 i − 1 ∑ j ′ = j + 1 k f i − s i z e , j ⋅ f s i z e , j ′ ⋅ ( i − 2 s i z e − 1 ) f_{i,j}=\sum_{size=1}^{i-1} \sum_{j'=j+1}^{k} f_{i-size,j} \cdot f_{size,j'} \cdot \binom{i-2}{size-1} fi,j=size=1∑i−1j′=j+1∑kfi−size,j⋅fsize,j′⋅(size−1i−2)
这个 j ′ j' j′ 的枚举搞个后缀和去掉，因此时间是 O ( n 2 k ) O(n^2k) O(n2k)。
