题目大意

有 $n$ 名选手，编号为 $1$ 到 $n$，他们被划分成若干个非空球队。球队的编号规则为：

将所有球队按照队中编号最小的选手排序；

球队编号从 $1$ 开始连续分配。

例如，若选手分组为 ${1}$、${2,3,5}$、${4,6}$，则：

$1$ 号选手所在队为 $1$ 号队；

$2$ 号选手所在队为 $2$ 号队；

$4$ 号选手所在队为 $3$ 号队。 对应的序列为 $1\ 2\ 2\ 3\ 2\ 3$。

我们称一个长度为 $n$ 的序列是合法的，当且仅当：

$a_1 = 1$；

设前 $i-1$ 位中出现的最大编号为 $m$，则 $a_i$ 可以是 $1, 2, \dots, m$ 中的任意一个数，或者是 $m+1$（表示新成立一个队伍）。

给定一个合法序列，要求计算它在所有合法序列按字典序排列中的排名（排名从 $1$ 开始），并将结果对 $1,000,007$ 取模。

算法思路

核心思想

利用动态规划预处理出从任意位置、任意当前最大编号出发，能生成的合法序列数目，再通过逐位确定法计算给定序列的字典序排名。

关键步骤

1. 预处理前缀最大值

定义数组 $x$，其中 $x[i]$ 表示序列前 $i$ 位中出现的最大编号。 递推计算：

$x[i]=max(x[i−1],a[i])$

$x[i]$ 用于在后续计算中限制第 $i$ 位可选的数字范围。

2. 倒序动态规划

定义 $f[m]$ 表示：从当前位开始，已知当前已出现的最大编号为 $m$ 时，剩余位置能够生成的合法序列数目。

考虑当前位可以填的数字：

若填入一个已经出现过的编号 $k \in [1, m]$，则有 $m$ 种选择，后续方案数为 $f[m]$；

若填入新编号 $m+1$，则后续方案数为 $f[m+1]$。

因此得到递推关系：

$f[m]=m⋅f[m]+f[m+1]$

初始化时，$f[m]$ 在序列末尾时取 $1$（表示唯一一种空序列）。

在实际实现中，我们从序列末尾向前逐位更新 $f$ 数组，使得 $f[m]$ 始终表示从当前位置往后的方案数。

3. 计算字典序排名

从第 $n$ 位到第 $1$ 位依次处理：

对于第 $i$ 位，枚举所有小于 $a_i$ 的可能取值 $j$；

若 $j$ 不超过 $x[i-1]$，则当前最大编号仍为 $x[i-1]$；

若 $j = x[i-1] + 1$，则最大编号更新为 $j$；

累加这些情况对应的方案数 $f[\max(j, x[i-1])]$ 到答案中。

最终，将累加结果 $+1$ 即为所求排名（因为序列本身也占一个位置）。

复杂度分析

时间复杂度：$O(n^2)$，主要来源于双重循环更新 $f$ 数组。

空间复杂度：$O(n)$，用于存储 $f$ 数组和前缀最大值数组。

总结

本题是经典的字典序排名问题，重点考察以下能力：

问题抽象与建模：将球队划分规则转化为序列合法性的形式化条件；

动态规划设计：定义合适的状态与递推关系，预处理方案数目；

字典序计数方法：利用逐位比较与累加的方式，高效计算目标序列的排名。

该解法在 $n \leq 10^4$ 的约束下可行，展示了组合数学与动态规划在计数类问题中的有效结合。