题解 P7292【「EZEC-5」Chasse Neige 加强版】
w33z8kqrqk8zzzx33
·
·
题解
良心出题人的良心题 /qq
官方题解怎么基本上跳过转移讲解啊
排列计数通常有两个 DP 方法：
- 按照顺序构造 DP，但是这里无法应用（存不了最后元素的值）
- 插入极值构造 DP
考虑维护第一值与第二值的关系，以及次后值与最后值关系。
- 令 a_{n\ k} 为长度为 n 的排列 (\pi_1,\pi_2,\dots,\pi_n) 个数，使得存在恰好 k 个巅峰并且 \pi_1<\pi_2,\pi_{n-1}>\pi_n。
- 令 b_{n\ k} 为长度为 n 的排列 (\pi_1,\pi_2,\dots,\pi_n) 个数，使得存在恰好 k 个巅峰并且 \pi_1<\pi_2,\pi_{n-1}<\pi_n。
- 令 c_{n\ k} 为长度为 n 的排列 (\pi_1,\pi_2,\dots,\pi_n) 个数，使得存在恰好 k 个巅峰并且 \pi_1>\pi_2,\pi_{n-1}>\pi_n。
- 令 d_{n\ k} 为长度为 n 的排列 (\pi_1,\pi_2,\dots,\pi_n) 个数，使得存在恰好 k 个巅峰并且 \pi_1>\pi_2,\pi_{n-1}<\pi_n。
则：
-
-
于是我们只需要往 a_{n\ k},b_{n\ k} 转移。
以下格式为 \text{旧排列类型}\rightarrow\text{新排列类型}。注意旧排列最后元素为 \pi_{n-1}。考虑转移，我们转移时插入 n 使巅峰变换更简介：
-
-
-
-
-
-
-
-
于是有递推
\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