[ZRC-524]全排列 / 题解
有一个 $1$ 到 $n$ 的排列 $p_1,p_2,p_3,...,p_n$,你会对它进行若干轮操作,每一轮操作,你会保留序列中极大的数,也就是说对于每个数字,如果它比相邻的数字都大,那么会被保留下来.比如一个排列 $(3,2,5,1,4,6)$,经过一轮操作之后序列变成 $(3,5,6)$,第二轮操作之后序列变成 $(6)$,经过恰好 $2$ 轮之后序列里只有一个元素.
请问有多少个长度为 $n$ 的序列,经过恰好 $k$ 次操作之后,序列里只有一个元素,由于答案很大,对一个素数 $P$ 取模.
⾸先考虑给定⼀个排列,我们计算它⼏次会被消掉.
考虑这个排列的笛卡尔树,那么当⼀个数它