Description

有一个 $1$ 到 $n$ 的排列 $p_1,p_2,p_3,…,p_n$,你会对它进行若干轮操作,每一轮操作,你会保留序列中极大的数,也就是说对于每个数字,如果它比相邻的数字都大,那么会被保留下来。比如一个排列 $(3,2,5,1,4,6)$,经过一轮操作之后序列变成 $(3,5,6)$,第二轮操作之后序列变成 $(6)$,经过恰好 $2$ 轮之后序列里只有一个元素。

请问有多少个长度为 $n$ 的序列,经过恰好 $k$ 次操作之后,序列里只有一个元素,由于答案很大,对一个素数 $P$ 取模。

Idea

⾸先考虑给定⼀个排列,我们计算它⼏次会被消掉。

考虑这个排列的笛卡尔树,那么当⼀个数它的左⼦树或者右⼦树都被消掉的时候,它就会和它的祖先直接相邻,也就是⼀个⽐它⼤的数。

所以记 $dp[u]$ 表示笛卡尔树中 $u$ 这个点的⼦树什么时候被全部消完。那么有 $dp[u]=\max (dp[l],dp[r],\min (dp[l],dp[r])+1)$。

我们得到了⼀个 $\Theta(n)$ 的判断⼀个序列多少轮被消完的⽅法。

可以把这个 $dp$ 的过程直接改成计数。

令 $dp[u][k]$ 表示⼤⼩为 $u$ 的⼦树,能存活 $k$ 轮。$dp$ 的时候枚举最⼤值在哪⾥,分成左右两边计算。

因为最多存活 $\log n$ 轮,时间复杂度为 $\Theta(n^2\log ^2 n)$。

Code

Leave a Reply to xgzepto

  1. Anonymous
    Dec 25, 2018

    hhh看到您T了好多次,

    Reply
    • xgzepto
      Dec 26, 2018

      赣州移动的 IP 呢。Anonymous 的时候记得挂梯子呢 ( •̀ ω •́ )

      Reply