E. 女孩排列 详细题解

题目核心理解

有一个长度为 $n$ 的排列被隐藏。 给定该排列的前缀最大值出现位置 $p_1<p_2<\dots<p_{m_1}$ 与后缀最大值出现位置 $s_1<s_2<\dots<s_{m_2}$。

你需要求出满足条件的合法排列数量，答案对 $10^9+7$ 取模。

前缀最大值：位置 $i$ 是前缀最大值，当且仅当 $a_i$ 严格大于它左边所有数。 后缀最大值：位置 $i$ 是后缀最大值，当且仅当 $a_i$ 严格大于它右边所有数。

---

核心思路

1. 关键合法性判定

• 排列的全局最大值 $n$ 一定是最后一个前缀最大值，同时也是第一个后缀最大值。
• 前缀最大值必须从 $1$ 开始，即 $p_1=1$。
• 后缀最大值必须以 $n$ 结束，即 $s_{m_2}=n$。
• 全局最大值位置必须唯一：$p_{m_1}=s_1$。

任意一条不满足，答案直接为 $0$。

2. 结构与计数规则

设全局最大值位置为 $pos = p_{m_1} = s_1$。

1. 左右数字分配 从 $1\sim n-1$ 中选出 $pos-1$ 个数放在最大值左边，剩余放在右边。 方案数为组合数 $\dbinom{n-1}{pos-1}$。

2. 左侧内部计数 前缀最大值序列将左侧划分为若干段。 每两个相邻前缀最大值之间的数可以任意排列，贡献为区间长度的阶乘。

3. 右侧内部计数 后缀最大值序列将右侧划分为若干段。 每两个相邻后缀最大值之间的数可以任意排列，贡献同样为区间长度的阶乘。

3. 总方案

合法排列数 = 组合数 × 左侧阶乘乘积 × 右侧阶乘乘积。

---

算法流程

1. 检查合法性：$p_1=1,\ s_{m_2}=n,\ p_{m_1}=s_1$，不满足则输出 $0$。
2. 预处理阶乘与逆元，用于快速求组合数和阶乘。
3. 计算组合数 $\dbinom{n-1}{pos-1}$。
4. 遍历前缀最大值序列，计算相邻位置间区间长度的阶乘乘积。
5. 遍历后缀最大值序列，计算相邻位置间区间长度的阶乘乘积。
6. 三者相乘并对 $10^9+7$ 取模，即为最终答案。

---

公式与复杂度分析

总答案公式：

$$ans = \dbinom{n-1}{pos-1} \times \left(\prod_{i=2}^{m_1} (p_i-p_{i-1}-1)!\right) \times \left(\prod_{i=2}^{m_2} (s_i-s_{i-1}-1)!\right) \pmod{10^9+7} $$

复杂度

• 预处理阶乘与逆元：$O(2\times10^5)$
• 每组测试用例：$O(m_1+m_2)$
• 总时间复杂度：$O(\sum n)$

可轻松处理 $n\le 2\times10^5$、多组数据 $\sum n \le 2\times10^5$ 的范围。