Second Gap（easy）：题解

思路

从右向左插入元素，记录新元素在当前后缀中从大到小的秩。全部合法秩序列与排列一一对应。若新元素的秩为 1 或 2，新后缀前两大位置是新位置 $i$ 与旧最大值位置 $a$；若秩至少为 3，旧前两大位置不变。

做法

令 $dp[a]$ 表示后缀 $i+1,\ldots,N$ 已满足要求且最大值位置为 $a$ 的方案数，初始 $dp[N]=1$。令 $a_0=i+D_i$：

• 秩为 1 时向 $next[i]$ 加 $dp[a_0]$；
• 秩为 2 时向 $next[a_0]$ 加 $dp[a_0]$；
• 当 $D_i=D_{i+1}$ 时，秩至少为 3 的 $N-i-1$ 种选择保持前两大不变，对每个 $a$ 向 $next[a]$ 加 $(N-i-1)dp[a]$。

三类秩互斥且完备，所以转移不重不漏。处理完后对所有最大值位置求和。

复杂度

时间复杂度 $O(N^2)$，空间复杂度 $O(N)$。模乘使用 64 位整数。

部分分

$N\le9$ 时枚举排列并逐后缀扫描前两大；$N\le80$ 时保留最大、次大位置有序对做 $O(N^3)$ DP。