自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:28:28，当前版本为作者最后更新于2021-02-28 18:12:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

良心出题人的良心题 /qq

官方题解怎么基本上跳过转移讲解啊

排列计数通常有两个 DP 方法：

1. 按照顺序构造 DP，但是这里无法应用（存不了最后元素的值）
2. 插入极值构造 DP

考虑维护第一值与第二值的关系，以及次后值与最后值关系。

1. 令 $a_{n\ k}$ 为长度为 $n$ 的排列 $(\pi_1,\pi_2,\dots,\pi_n)$ 个数，使得存在恰好 $k$ 个巅峰并且 $\pi_1<\pi_2,\pi_{n-1}>\pi_n$。
2. 令 $b_{n\ k}$ 为长度为 $n$ 的排列 $(\pi_1,\pi_2,\dots,\pi_n)$ 个数，使得存在恰好 $k$ 个巅峰并且 $\pi_1<\pi_2,\pi_{n-1}<\pi_n$。
3. 令 $c_{n\ k}$ 为长度为 $n$ 的排列 $(\pi_1,\pi_2,\dots,\pi_n)$ 个数，使得存在恰好 $k$ 个巅峰并且 $\pi_1>\pi_2,\pi_{n-1}>\pi_n$。
4. 令 $d_{n\ k}$ 为长度为 $n$ 的排列 $(\pi_1,\pi_2,\dots,\pi_n)$ 个数，使得存在恰好 $k$ 个巅峰并且 $\pi_1>\pi_2,\pi_{n-1}<\pi_n$。

则：

1. $b_{n\ k}$ 与 $c_{n\ k}$ 具有一一对应：$(\pi_1,\pi_2,\dots,\pi_n)\Leftrightarrow(\pi_n,\pi_{n-1},...,\pi_1)$。
2. $a_{n\ k}$ 与 $d_{n\ k-1}$ 具有一一对应：$(\pi_1,\pi_2,\dots,\pi_n)\Leftrightarrow(n+1-\pi_1,n+1-\pi_2,\dots,n+1-\pi_n)$。这是因为每一个巅峰（除了最后一个）都有恰好一个紧接下来的逆巅峰，每一个逆巅峰都有恰好一个紧接下来的巅峰。

于是我们只需要往 $a_{n\ k},b_{n\ k}$ 转移。

以下格式为 $\text{旧排列类型}\rightarrow\text{新排列类型}$。注意旧排列最后元素为 $\pi_{n-1}$。考虑转移，我们转移时插入 $n$ 使巅峰变换更简介：

1. $a_{n-1\ k}\rightarrow a_{n\ k}$ 有 $2k$ 方案；不会产生新巅峰当且仅当插入在紧挨着一个旧巅峰，覆盖了旧巅峰。
2. $a_{n-1\ k-1}\rightarrow a_{n\ k}$ 有 $n-1-1-2(k-1)=n-2k$ 方案；需要插入在旧排列 里面 并且不能挨着一个巅峰，这样会新构造一个巅峰。
3. $b_{n-1\ k-1}\rightarrow a_{n\ k}$ 有 $1$ 方案；插入在旧排列 $\pi_{n-2}$ 和 $\pi_{n-1}$ 之间会产生恰好一个巅峰。
4. $c_{n-1\ k-1}\rightarrow a_{n\ k}$ 有 $1$ 方案；插入在旧排列 $\pi_1$ 和 $\pi_2$ 之间会产生恰好一个巅峰。
5. $b_{n-1\ k}\rightarrow b_{n\ k}$ 有 $2k+1$ 方案；与 $1$ 转移同理，也可以插入在旧排列 $\pi_{n-1}$ 后面。
6. $b_{n-1\ k-1}\rightarrow b_{n\ k}$ 有 $n-1-1-2(k-1)-1=n-2k-1$ 方案；基本和 $2$ 同理，但是需要减 $1$ 因为不能在旧 $\pi_{n-2},\pi_{n-1}$ 之间插入。
7. $a_{n-1\ k}\rightarrow b_{n\ k}$ 有 $1$ 方案；插入在旧排列 $\pi_{n-1}$ 后面。
8. $d_{n-1\ k-1}\rightarrow b_{n\ k}$ 有 $1$ 方案；插入在旧排列 $\pi_1$ 和 $\pi_2$ 之间，同时会产生一个新巅峰。

于是有递推

$$\begin{cases}a_{n\ k}=2ka_{n-1\ k}+(n-2k)a_{n-1\ k-1}+b_{n-1\ k-1}+c_{n-1\ k-1}\\b_{n\ k}=(2k+1)b_{n-1\ k}+(n-2k-1)b_{n-1\ k-1}+a_{n-1\ k}+d_{n-1\ k-1}\end{cases} $$

采用以上一一对应：

$$\begin{cases}a_{n\ k}=2ka_{n-1\ k}+(n-2k)a_{n-1\ k-1}+2b_{n-1\ k-1}\\b_{n\ k}=(2k+1)b_{n-1\ k}+(n-2k-1)b_{n-1\ k-1}+2a_{n-1\ k}\end{cases} $$

不 感 觉 很 类 似 吗 ？

定 $f_{n\ k}$，其中 $f_{n\ 2k}=a_{n\ k}$，$f_{n\ 2k+1}=b_{n\ k}$，则 $a_{n\ k}$ 在 $f$ 里“上一个”元素是 $b_{n\ k-1}$，$b_{n\ k}$ 在 $f$ 里“上一个”元素是 $a_{n\ k}$。

于是有

$$f_{n\ k}=kf_{n-1\ k}+(n-k)f_{n-1\ k-2}+2f_{n-1\ k-1} $$

考虑 $f_{n\ n-1}$ 代表什么；替换回去得到 $f_{2n\ 2n-1}=f_{2n\ 2(n-1)+1}=b_{2n\ n-1}$；$f_{2n+1\ 2n}=a_{2n+1\ n}$。

套会原始，得到 $f_{2n\ 2n-1}=b_{2n\ n-1}$ 为满足相邻比较是 <><><...>< 的排列，$f_{2n+1\ 2n}=a_{2n+1\ n}$ 位满足 <><><...><> 的排列。

这些是 ”Alternating permuation numbers“，由 Andre 定理，这数列由指数生成函数 $[\frac{x^n}{n!}](\tan(x)+\sec(x))$ 给出。于是

$$f_{n\ n-1}=n+\sec(x))$$

考虑定义 $f'_{n\ d}=f_{n\ n-d}$，则：

$$f'_{n\ d}=(n-d)f_{n-1\ k}+df_{n-1\ k-2}+2f_{n-1\ k-1} $$$$f'_{n\ d}=(n-d)f'_{n-1\ d-1}+df'_{n-1\ d+1}+2f'_{n-1\ d} $$$$\begin{cases}f'_{n\ 1}=n+\sec(x))\\f'_{n-1\ d+1}=\frac{f'_{n\ d}-(n-d)f'_{n-1\ d-1}-2f'_{n-1\ d}}{d}\end{cases} $$

问题想求 $a_{n\ k}=f_{n\ 2k}=f'_{n\ n-2k}$，递推即可。

最优解 /qq