听说同学用容斥写这题卡了几天，我试着从 DP 的角度想很快就过了。看到题解区没人与我的思路相同，于是前来写一篇题解。
题目传送门
既然是从 DP 的角度考虑，我们先想一想如何设计状态。题目要求 DP 一个排列，一个自然的想法是状压，但在本题的数据范围下显然无法通过。观察到题目只不关心排列中各个数具体的值，而只关心排列中各数的大小关系，故我们可以不在 DP 状态中记录数值而是记录排名。
如果您不是很明白“记录当前数在已考虑数中的排名”的实现，或者是第一次见到这个 Trick，可以先写一写 AT_dp_t Permutation 和 P2467 [SDOI2010] 地精部落 两道题。
总之，我们可以设计状态：当前考虑到排列的某一个前缀，其中有 i 个数小于 x+0.5，j 个数大于 x+0.5，Bessie 上一次回答的是 LO/HI 的方案数和所有方案中说出过的子串 HILO 总数，分别记为 c_{i,j,0/1} 和 d_{i,j,0/1}。接下来考虑如何转移（即往排列中插入新的数）：
- 上一个回答是
LO，这次插入的数小于 x+0.5：
\begin{aligned} d_{i+1,j,0} &\leftarrow d_{i+1,j,0} + (i+1) d_{i,j,0} \\ c_{i+1,j,0} &\leftarrow c_{i+1,j,0} + (i+1) c_{i,j,0} \end{aligned}
- 上一个回答是
LO，这次插入的数大于 x+0.5，但是被 Elsie 跳过：
\begin{aligned} d_{i,j+1,0} &\leftarrow d_{i,j+1,0} + j \cdot d_{i,j+1,0} \\ c_{i,j+1,0} &\leftarrow c_{i,j+1,0} + j \cdot c_{i,j+1,0} \end{aligned}
- 上一个回答是
LO，这次插入的数大于 x+0.5，没有被 Elsie 跳过：
\begin{aligned} d_{i,j+1,1} &\leftarrow d_{i,j+1,1} + d_{i,j,0} \\ c_{i,j+1,1} &\leftarrow c_{i,j+1,1} + c_{i,j,0} \end{aligned}
- 上一个回答是
HI，这次插入的数大于 x+0.5：
\begin{aligned} d_{i,j+1,1} &\leftarrow d_{i,j+1,1} + (j+1) d_{i,j,1} \\ c_{i,j+1,1} &\leftarrow c_{i,j+1,1} + (j+1) c_{i,j,1} \end{aligned}
- 上一个回答是
HI，这次插入的数小于 x+0.5，但是被 Elsie 跳过：
\begin{aligned} d_{i+1,j,0} &\leftarrow d_{i+1,j,0} + i \cdot d_{i,j,1} \\ c_{i+1,j,0} &\leftarrow c_{i+1,j,0} + i \cdot c_{i,j,1} \end{aligned}
- 上一个回答是
HI，这次插入的数小于 x+0.5，没有被 Elsie 跳过：
\begin{aligned} d_{i+1,j,0} &\leftarrow d_{i+1,j,0} + d_{i,j,1} + {\color{ff0000}c_{i,j,1}} \\ c_{i+1,j,0} & \leftarrow c_{i+1,j,0} + c_{i,j,1} \end{aligned}
标红的部分计算了 HILO 的出现次数，一定要记得加上。
至于初始值，只需将 c_{1,0,0} 和 c_{0,1,1} 置为 1，剩下的全零即可。最终的答案就是 d_{x,n-x,0} + d_{x,n-x,1}。然后我们就可以愉快地开始 DP 辣。同时别忘了滚动数组，否则会爆空间。提交记录