毛营 2017（冬）Xiaoxu Guo Contest 5 H 题解 - Permutation and noitatumreP

x义x · 2021-10-26 17:43:53 · 个人记录

更坏的阅读体验

题目大意.

考虑一个排列 p，我们把它 reverse 后接在它自己的后面得到了一个新序列 q=pp^r。

如果不存在 a<b<c<d 满足 q(a)<q(c)<q(d)<q(b)，那么我们称 p 是一个 无 1423 的排列。

问，有多少 1\sim n 的无 1423 的排列。

真是一道不可多得的分类讨论好题！

我们断言，设答案为 f(n)，如果 n\ge 4，有

我们可以通过分类讨论来证明这一结论。

Case #1: p_1=n

显然这时 p_1 "完全惰性"，不可能出现在四元组中，p 无 1423 当且仅当 p_2\sim p_n 无 1423。

此种 p 的数量就是 f(n-1)。

Case #2: p_1= n-1

此时 n 的位置非常有限，因为 n 和 n-1 很容易构成四元组中的 4 和 3。事实上，p_2=n。那么这时 p_1,p_2 也就完全惰性了。

此种 p 的数量就是 f(n-2)。

Case #3: p_1=1

同理，1 和 2 很容易构成 1 和 2，于是 p_2=2，同理 p_3=3，……，p_{n-2}=n-2。但 n 和 n-1 可以交换。

此种 p 的数量就是 2。

Case #4: p_1=i，其中 i\in[3,n-2]

我们来说明，p_2=i+1。

首先它不能是 1。若不然，要么有四元组 p_2,i+1,2/p_1 要么有四元组 p_2,n/2,i+1（其中 / 是 p 和 p^r 的分界线）。

其次它不能是 2\sim i-1。若不然，必有四元组 p_2,n/1,p_1。

第三它不能是 i+2\sim n-1。若不然，必有四元组 p_1,n/i+1,p_2。

最后它不能是 n。若不然，必有四元组 p_1,p_2,1/2。

同理，p_3=i+2，……，但 n 和 n-1 可以交换。前面这一段上升序列对后面的部分完全惰性。

故此种 p 的数量是 \sum_{i=2}^{n-3}2f(i)。

Case #5: p_1=2

此时有 p_2\in\{1,3\}。

它不能是 n。否则有四元组 p_1,p_2,3/n-1。

它也不能是 [4, n-1] 中的任何一个，否则有四元组 1/n,3,p_2 或 p_1,n,3/p_2 之一。

于是我们就得到了两个 subcase：

Subcase #5.1: p_1=2,p_2=1

此时有 p_3=3。理由类似。

同理，p_4=4，……，但 n 和 n-1 可以交换。

此种 p 的数量是 2。

Subcase #5.2: p_1=2,p_2=3

此时有 p_3=\{1,4\}。理由类似。

于是一直往下填，每当你选择 1 时就立刻转化为上一种 subcase，不难发现你能选择的就是 1​ 填哪里。

此种 p 的数量是 2(n-2)。

终于讨论完了！剩下的工作已经很明显了。

怎么还要快速线性递推啊草