题目解析

1. 问题重述

我们有 n 个位置（小矮人），每个位置上的帽子高度是一个 1 到 n 的排列。
对于第 i 个小矮人，他报告了一个值 h_i，表示 h_i 这个帽子高度 出现在位置 i-1、i 或 i+1 中（即他自己、左邻居或右邻居）。

我们要统计所有满足这些条件的排列数，模 10^9+7。

2. 约束转换

对于每个可能的帽子高度 v（1 ≤ v ≤ n），它必须出现在至少一个小矮人报告的位置的邻域内。

更具体地说，设帽子高度 v 出现在位置 p_v（1 ≤ p_v ≤ n），那么必须存在某个 i 使得：

• h_i = v
• |p_v - i| ≤ 1（即 p_v 在 i 的邻域内）

3. 对每个高度 v 的可行位置范围

对于高度 v，考虑所有报告 h_i = v 的 i，那么 p_v 必须至少在一个 i 的邻域内。

所以：

• 左边界 l[v] = max{1, i-1} 对所有 i 取最大值
• 右边界 r[v] = min{n, i+1} 对所有 i 取最小值

如果 l[v] > r[v]，则无解。

4. 问题转化为区间放置问题

现在问题变成：

• 有 n 个高度 1...n，每个高度 v 必须放在区间 [l[v], r[v]] 内的某个位置
• 每个位置只能放一个高度
• 问排列数

这是一个带区间限制的排列计数问题。

5. 特殊情况

• 如果某个高度 v 没有被任何小矮人报告（即 l[v] 仍为初始值 -inf），那么它可以放在任意位置，但必须满足排列的唯一性。
• 在代码中，cnt 统计这种"自由"的高度数量。

6. 动态规划思路

可以使用状压 DP：

• 状态 dp[S]：S 是一个 3 位的位掩码（0~7），表示当前处理到某个位置时，最近 3 个位置（包括当前）的帽子高度是否已经被分配。
• 我们按位置 1...n 顺序处理。
• 对于每个位置 i，我们考虑所有右端点 r[v] = i 的高度 v，它们必须在这个位置或之前被放置，并且放置位置 ≥ l[v]。

7. 算法流程

1. 计算区间
   对每个高度 v，计算 l[v] 和 r[v]。
   如果 l[v] > r[v]，输出 0。

2. 按右端点分组
   将高度按照右端点分组。

3. DP 初始化
   初始状态表示还没有处理任何位置时，"最近3个位置"都视为已占用（虚拟位置）。

4. 按位置顺序 DP

   • 首先扩展状态：移动到下一个位置，最老的位置移出窗口。
   • 对于每个在位置 i 结束的高度区间，进行放置：在窗口内选择一个空位放置这个高度。

5. 处理自由高度
   最后，自由高度可以任意排列在剩余空位，所以乘以 cnt!。

8. 举例（样例 1）

输入： 4 2 4 2 1

高度 1：出现在位置 4 → 区间 [3, 4]
高度 2：出现在位置 1, 3 → 区间 [max(1,0)=1, min(4,4)=4] 即 [1,4]
高度 3：未出现 → 自由
高度 4：出现在位置 2 → 区间 [1, 3]

DP 过程会统计出 3 种合法排列。

9. 总结

这个解法核心是：

• 将问题转化为区间放置问题
• 使用滑动窗口状压 DP，按右端点处理区间
• 对自由高度最后乘阶乘

这是一个典型的带约束排列计数问题，通过区间限制和动态规划可以有效解决。