数位DP-基础讲解

题目大意#

简单来说，题目会给我们两个正整数 $a$ 和 $b$，我们需要统计出在 $[a, b]$ 这个闭区间内，所有的整数中，数字 $0, 1, 2, \dots, 9$ 分别出现了多少次。

例如，在 $[1, 99]$ 区间内，数字 $1$ 在 $1, 10, 11, \dots, 19, 21, \dots, 91$ 等数字中出现，我们需要计算它出现的总次数。

思路分析#

当看到数据范围 $1 \le a \le b \le 10^{12}$ 时，逐个遍历数字并统计的方法显然会超时。这种与“数字位数”强相关且数据范围极大的计数问题，正是数位 DP 的用武之地。

解决这类区间 $[a, b]$ 的问题，我们通常会使用一个经典的 前缀和 思想：

求 $[a, b]$ 范围内的答案，可以转化为 (1 到 b 的答案) - (1 到 a-1 的答案)。

这样，问题就简化为如何实现一个函数 count(n, d)，用来计算在 $[1, n]$ 范围内，目标数字 d 出现的总次数。

为了实现 count(n, d)，我们将采用 从高位到低位 依次填数的方式来构造 $[1, n]$ 范围内的所有数字。我们使用一个递归函数（通常命名为 dfs）来完成这个过程，并通过记忆化来优化。在递归的每一步，我们需要携带一些关键信息（状态），以确保我们构造的数字是合法的，并且能够正确地进行计数。

状态设计 (DP Definition)#

在我们的 dfs 函数中，需要定义以下几个参数来构成我们的 DP 状态：

dfs(int pos, int sum, bool lead, bool limit)

• int pos: 表示我们当前正在处理的是数字的第几位（从高位向低位）。例如，对于数字 987，pos=3 就代表最高位的百位。
• int sum: 这是一个累加器，记录到目前为止，我们正在统计的目标数字已经出现了多少次。
• bool lead: 一个布尔标记，用于判断当前位及之前是否是前导零。例如，构造三位数时，007 中的前两个0就是前导零，不应计入数字0的统计。一旦我们填入一个非零数字，lead 标志就会变为 false。
• bool limit: 一个布尔标记，用于判断当前位的选择是否受到上限的限制。例如，要统计 $[1, 199]$ 内的数，当我们处理百位时，若填了 1，则十位最多只能填 9；但如果百位填了 0（即构造一个两位数），那么十位就可以从 0 到 9 任意选择，limit 就会变为 false。

代码讲解#

我们来详细分析一下这份现代 C++ 风格的代码。

1. 主体框架

1
i64 a, b;
2
cin >> a >> b;
3
for (int i = 0; i < 10; i++) {
4
    now = i; // now 是一个外部变量，记录当前要统计的数字
5
    cout << f(b) - f(a - 1) << " \n"[i == 9];
6
}

这里清晰地展示了 f(b) - f(a - 1) 的思想。通过一个循环，依次将 $0 \\sim 9$ 设为目标数字 now，并计算其出现次数。

2. f(x) 函数

1
auto f = [&](i64 x) -> i64 {
2
    int len = 0;
3
    num = to_string(x);
4
    dp.assign(N, vector<i64>(N, -1)); // 重置 dp 数组
5
    return dfs(dfs, 0, 0, true, true); // 开始递归
6
};

这是数位 DP 的入口。它首先将数字 x 拆解成数位（注意这里 num[1] 是个位，num[len] 是最高位）。然后调用 dfs 开始递归，并传入初始状态：从最高位 len 开始，初始 sum 为 0，lead 和 limit 均为 true。

3. 核心 dfs 函数

1
auto dfs = [&](auto &self, int pos, int sum, bool lead, bool limit) -> i64 {
2
    i64 ans = 0;
3
    // 递归边界：所有位都填完了，返回累加的结果
4
    if (pos == num.lenght()) return sum;
5
    // 记忆化：只有在不受 lead 和 limit 影响的通用状态下才能使用
6
    if (!lead && !limit && dp[pos][sum] != -1) return dp[pos][sum];
7

8
    int up = limit ? num[pos] : 9; // 确定当前位能填的数的上限
9

10
    for (int i = 0; i <= up; ++ i) {
11
        // 分情况讨论并进行递归
12
        if (i == 0 && lead) {
13
            // 情况1: 当前是前导零
14
            ans += self(self, pos + 1, sum, true, limit && i == up);
15
        } else if (i == now) {
16
            // 情况2: 当前数字是我们要统计的目标 now
17
            ans += self(self, pos + 1, sum + 1, false, limit && i == up);
18
        } else { // i != now
19
            // 情况3: 普通数字
20
            ans += self(self, pos + 1, sum, false, limit && i == up);
21
        }
22
    }
23

24
    if (!lead && !limit) {
25
        dp[pos][sum] = ans; // 记录通用状态的结果
26
    }
27
    return ans;
28
};

• 递归边界: pos == 0，表示一个完整的数构造完毕。此时我们不能返回 1，而应该返回 sum。因为 dfs 的返回值是 当前状态下能构造出的所有合法数字中，目标数字 now 出现的总次数。
• 记忆化: if (!lead && !limit && dp[pos][sum] != -1) 是记忆化的关键。只有当状态是“泛化”的（即后续位数可以从 0-9 自由选择，也不再是前导零），其计算结果才可以被复用。
• 循环与转移:
  • up 确定了当前位 pos 的数字 i 的上限。
  • 循环内部的 if-else 分情况讨论：
    • i == 0 && lead: 这是前导零，不计入 0 的个数，所以 sum 不变，lead 标志继续为 true。
    • i == now: 填入的数字是目标数字 now，所以下一层的 sum 要加 1，同时 lead 变为 false。
    • i != now: 普通情况，sum 不变，lead 变为 false。
  • limit && i == up: 这个表达式用于决定下一层的 limit 状态。只有当这一位本身受限(limit为true)，并且我们填入的数字达到了上限(i == up)，下一位才会继续受限。

总结#

这道题是数位 DP 的一个完美模板。通过它，我们学习到了：

1. f(b) - f(a-1) 的经典区间转化技巧。
2. 数位 DP 的核心状态设计：pos, state(此题为sum), lead, limit。
3. 记忆化搜索是数位 DP 的常见实现方式，逻辑清晰，代码简洁。
4. 处理 前导零 是一个需要特别注意的细节，尤其是在统计数字 0 时。

题目大意解析#

本题的核心是理解 “windy 数” 的定义：一个不含前导零的正整数，其相邻两个数字的差的绝对值至少为 $2$。我们需要计算在给定区间 $[a, b]$ 内有多少个这样的 windy 数。

例如，$13$ 是 windy 数，因为 $|1-3|=2 \ge 2$。$12$ 则不是，因为 $|1-2|=1 < 2$。

思路分析#

题目依然是区间计数问题，数据范围也暗示了需要使用数位 DP。我们还是沿用 solve(b) - solve(a-1) 的经典思路，将问题核心聚焦于如何实现 solve(x) 函数，即统计 $[1, x]$ 中 windy 数的数量。

与上一题不同的是，这里出现了一个新的约束条件：“相邻两个数字之差至少为 2”。这个 “相邻” 的概念是关键。当我们在 dfs 中为当前位 pos 选择一个数字 i 时，我们必须知道它的前一位（即 pos+1 位）的数字是什么，才能判断 i 是否合法。

因此，我们的 DP 状态必须能够记录前一位数字的信息。

状态设计 (DP Definition)#

我们在上一题的基础上，为 dfs 函数增加一个参数来记录前一位的数字。

dfs(int pos, int pre, bool lead, bool limit)

• int pos: 与之前相同，表示当前处理的位数。
• int pre: 新增状态。记录前一位（更高位）填的数字。这是本题的核心。为了处理首位数字（它没有前一位），我们可以用一个特殊值（如 10 或 -1）来表示。
• bool lead: 前导零标记。当 lead 为 true 时，说明前面都是 0，此时对当前位没有 “相邻差” 的约束。
• bool limit: 上限限制标记，含义与之前完全相同。

代码讲解#

下面是针对本题的参考实现。

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long; // 使用 i64 作为 long long 的别名，方便书写
4

5
int main() {
6
    // 优化 C++ 输入输出流的性能
7
    ios::sync_with_stdio(false);
8
    cin.tie(nullptr);
9

10
    i64 a, b; // 定义两个长整型变量 a 和 b，用于存储输入的区间
11
    cin >> a >> b; // 读取区间的左右端点
12

13
    // 定义一个 lambda 函数 f，用于计算 [0, x] 中满足条件的数的个数
14
    auto f = [&](i64 x) -> i64 {
15
        string s = to_string(x); // 将数字 x 转换为字符串
16
        int len = s.size();      // 获取字符串的长度，即数字的位数
17
        // 定义一个二维向量 dp 用于记忆化搜索
18
        // dp[pos][pre] 表示当前处理到第 pos 位，前一位是 pre 的情况下，后面可以构造出的满足条件的数的个数
19
        vector dp(len, vector<i64>(10, -1));
20

21
        // 定义一个递归的 lambda 函数 dfs，用于进行数位 DP
22
        // 参数：
23
        // self: 用于递归调用自身
24
        // pos: 当前处理的位数（从左到右，0-indexed）
25
        // pre: 前一位的数字
26
        // limit: bool 类型，表示当前位是否受到 x 的限制（例如 x=123，处理到百位时最大只能是1）
27
        // lead: bool 类型，表示当前位是否是前导零
28
        auto dfs = [&](auto &&self, int pos, int pre, bool limit, bool lead) -> i64 {
29
            // 如果所有位都处理完了，说明找到一个满足条件的数，返回 1
30
            if (pos == len) {
31
                return 1;
32
            }
33

34
            // 记忆化：如果当前状态没有限制，不是前导零，并且之前已经计算过，则直接返回结果
35
            if (pre >= 0 && !limit && !lead && dp[pos][pre] != -1) {
36
                return dp[pos][pre];
37
            }
38

39
            i64 res = 0; // 用于累加当前状态下满足条件的数的个数
40
            // 确定当前位的上限 up
41
            // 如果受到限制，则 up 为 s[pos] 对应的数字；否则为 9
42
            int up = (limit ? s[pos] - '0' : 9);
43

44
            // 遍历当前位所有可能的数字 i
45
            for (int i = 0; i <= up; i++) {
46
                // 处理前导零的情况
47
                if (i == 0 && lead) {
48
                    // 如果当前是前导零，那么下一位仍然可以看作是前导零，pre 设为 -1 表示没有前一位
49
                    res += self(self, pos + 1, -1, limit && i == up, true);
50
                } else {
51
                    // 非前导零的情况
52
                    // 判断当前位 i 和前一位 pre 的差的绝对值是否大于等于 2
53
                    if (abs(i - pre) >= 2) {
54
                        // 递归到下一位
55
                        // limit && i == up: 只有在当前位受限且 i 取到上限时，下一位才受限
56
                        // lead: false，因为已经填了非零数字
57
                        res += self(self, pos + 1, i, limit && i == up, false);
58
                    }
59
                }
60
            }
61

62
            // 如果没有限制且不是前导零，将结果存入 dp 表中
63
            if (pre >= 0 && !limit && !lead) {
64
                dp[pos][pre] = res;
65
            }
66

67
            return res; // 返回当前状态下满足条件的数的总数
68
        };
69

70
        // 从第 0 位开始搜索，初始时没有前一位（pre=-1），受限制（limit=true），是前导零（lead=true）
71
        return dfs(dfs, 0, -1, true, true);
72
    };
73

74
    // 区间 [a, b] 中满足条件的数的个数等于 f(b) - f(a - 1)
75
    cout << f(b) - f(a - 1) << "\n";
76

77
    return 0;
78

79
}

1. f(x) 函数:

   • 与之前类似，它负责拆分数字并启动 dfs。
   • dfs(dfs, len, -1, true, true): 初始调用 dfs。pre 参数传入 -1，这是一个“虚拟”的前置数字，因为它不影响任何一位的决策（加了判断）。

2. dfs 函数:

   • Base Case: if (pos == 0) return 1; 如果成功填完所有位，说明找到一个合法的 windy 数，返回 1。
   • Memoization: if (pre >= 0 && !limit && !lead && dp[pos][pre] != -1)。记忆化的状态现在是 (pos, pre)。
   • Transitions:
     • if (lead): 如果处于前导零状态。
       • 若填 0，则下一位依然是 lead 状态，pre 依然是虚拟值 -1。
       • 若填 1-9，则下一位 lead 变为 false，且 pre 更新为当前数字 i。
     • else: 如果不处于前导零状态。
       • 必须检查 abs(i - pre) >= 2。只有满足该条件的数字 i 才能被选择，并进入下一层递归。

总结#

通过 “windy 数” 这个问题，我们学到了数位 DP 一个非常重要的扩展思路：当题目约束与相邻数位有关时，需要将前一位（或后一位）的信息加入到 DP 状态中。这个思想可以推广到更复杂的问题，比如要求数位满足某种特定模式或性质的场景。

题目大意解析#

题目定义了一种变换操作：将一个正整数 x 替换为其二进制表示中 1 的个数（即 popcount(x)）。例如，13 的二进制是 1101，有 3 个 1，所以 13 经过一次操作后会变成 3。

如果一个数 x 经过 恰好 k 次 这样的操作后，第一次变为 1，那么 x 就被称为“特殊数”。

我们需要求解在 $[1, n]$ 的范围内有多少个这样的特殊数。注意，n 是以二进制字符串的形式给出的，其长度可能高达 1000。

思路分析#

1. 建模变换过程

首先，我们需要把“经过 k 次操作变为 1”这个条件数学化。 让我们定义一个函数 $g(i)$ 表示将数字 $i$ 通过上述操作变为 1 所需的最小操作次数。 根据定义，我们有：

• $g(1) = 0$ (因为它已经是 1，需要 0 次操作)
• 对于 $i > 1$, $i$ 会先变为 popcount(i)，这消耗了 1 次操作，之后还需要 $g(\text{popcount}(i))$ 次操作。所以，$g(i) = g(\text{popcount}(i)) + 1$。

现在，我们来分析一个数 x 变为 1 的过程。

• 第一次操作: $x \to \text{popcount}(x)$
• 后续操作: $\text{popcount}(x)$ 再经过 $g(\text{popcount}(x))$ 次操作变为 1。

所以，将 x 变为 1 的总操作次数就是 $1 + g(\text{popcount}(x))$。 题目要求的条件是总操作次数为 k，因此，一个数 x > 1 是特殊数的充要条件是：

$1 + g(\text{popcount}(x)) = k$

对于特殊情况 x = 1，它需要 0 次操作，所以它在 k=0 时是一个特殊数。

2. 转化为数位 DP

问题转化成了：统计在 $[1, n]$ 范围内，有多少个数 x，其二进制中 1 的个数 c = popcount(x) 满足 $1 + g(c) = k$。

由于 n 的范围非常大（二进制长度达 1000），我们自然想到使用数位 DP。

• 预计算: n 的长度不超过 1000，所以任何小于 n 的数的 popcount 也不会超过 1000。我们可以预先计算出 g[1] 到 g[1000] 的所有值。
• 数位 DP: 我们将从高位到低位（从左到右）构建一个二进制数，确保它小于等于 n，同时统计其 1 的个数，并检查这个个数是否满足条件。

3. 组合数学优化

在标准的数位 DP 过程中，当我们某一位的选择不受 n 的限制时（即 limit 标志变为 false），后续的所有位都可以自由地填 0 或 1。在这种情况下，逐位递归就显得效率低下了。

我们可以使用组合数学进行优化。假设我们当前处理到第 pos 位，已经统计了 cnt 个 1，并且 limit 为 false。剩下的还有 len - pos 位需要填写。如果我们计划在剩下的位数中再填 j 个 1，那么总的 1 的个数就是 cnt + j。我们检查 cnt + j 是否满足特殊数的条件。如果满足，那么有多少种方法可以在 len - pos 个位置中选择 j 个位置填 1 呢？答案是组合数 $C(\text{len - pos}, j)$。

我们只需遍历所有可能的 j (从 0 到 len - pos)，将满足条件的组合数累加起来，就可以一次性计算出所有从此状态出发的合法数字数量。

代码讲解#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
constexpr int M = 1e9 + 7;
6

7
const int N = 1e3 + 5;
8
i64 fact[N], ifact[N];
9
// ... 组合数相关的预计算函数 power, init, C ...
10

11
int main() {
12
    // ...
13
    string s;
14
    int k;
15
    cin >> s >> k;
16

17
    if (k == 0) { // k=0 只有 x=1 这一个解
18
        cout << 1 << "\n";
19
        return 0;
20
    }
21

22
    init(); // 预计算组合数
23

24
    vector<int> g(1010);
25
    g[1] = 0;
26
    for (int i = 2; i <= 1000; i++) {
27
        g[i] = g[__builtin_popcount(i)] + 1; // 预计算 g(i)
28
    }
29

30
    int len = s.size();
31
    i64 ans = 0;
32
    // C++23风格的递归lambda
33
    auto dfs = [&](this auto &&self, int pos, bool limit, int cnt) -> void {
34
        if (pos == len) { // 到达末尾
35
            if (cnt > 0 && g[cnt] + 1 == k) {
36
                ans = (ans + 1) % M;
37
            }
38
            return;
39
        }
40

41
        if (limit) { // 受限情况，只能递归
42
            for (int i = 0; i <= s[pos] - '0'; i++) {
43
                self(pos + 1, limit && (i == s[pos] - '0'), cnt + (i == 1));
44
            }
45
        } else { // 不受限情况，组合数学优化
46
            for (int j = 0; j <= len - pos; j++) {
47
                if (cnt + j > 0 && g[cnt + j] + 1 == k) {
48
                    ans = (ans + C(len - pos, j)) % M;
49
                }
50
            }
51
        }
52
    };
53

54
    dfs(0, true, 0);
55

56
    // 最终答案需要修正
57
    if (k == 1) {
58
        ans = (ans - 1 + M) % M;
59
    }
60

61
    cout << ans << "\n";
62
    return 0;
63
}

1. 预计算 g 数组: g[i] = g[__builtin_popcount(i)] + 1; 这行代码完美地实现了我们之前推导的递推关系。
2. k=0 特判: k=0 的情况只对应 x=1，直接输出 1 并退出。后续的 dfs 逻辑处理的是 k \ge 1 的情况。
3. dfs 函数:
   • 状态为 (pos, limit, cnt)，分别代表当前位数、是否受限、已有的 1 的个数。
   • limit 分支: 当 limit 为 true 时，当前位 i 最大只能取到 s[pos] - '0'。我们继续递归，并根据 i 是否等于上限来更新下一位的 limit 标志。
   • !limit 分支: 这是优化的核心。我们不再递归，而是直接计算。len-pos是剩余位数，j 是我们打算在这些位中放的 1 的个数。如果总的 1 的个数 cnt+j 满足条件 g[cnt+j]+1 == k，我们就将方案数 C(len - pos, j) 加入答案。
   • Base Case: 在 pos == len 时，我们已经构建了一个完整的数。此时 cnt 就是总的 popcount。我们检查 cnt 是否满足条件 g[cnt]+1 == k。注意要排除 cnt=0 的情况，因为它对应 x=0，而题目要求正整数。
4. 最终答案修正:
   • dfs 统计的是 $[0, n]$ 范围内的数。
   • 当 k=1 时，需要的条件是 g(popcount(x)) = 0，这意味着 popcount(x) = 1。
   • dfs 会统计所有 popcount(x)=1 的数，包括 x=1。
   • 但是，x=1 是一个 k=0 的特殊数，不应该被 k=1 的情况统计。因此，当 k=1 时，我们需要从答案中减去 1。

总结#

本题是一个非常精彩的数位 DP 题目，它教会我们：

1. 如何将一个看似复杂的操作计数问题，通过函数建模，转化为对 popcount 的简单约束。
2. 在数位 DP 中，当 limit 约束解除后，可以使用组合数学进行剪枝和优化，极大地提高了计算效率。
3. 注意处理问题的边界条件，如 k=0、x=1 等，它们往往需要特判或在最终答案中进行修正。

题目大意解析#

这道题的核心是理解一种特殊的“球队分配”方案。有 $n$ 名选手，要被分成若干个非空队伍。队伍的编号规则很特别：

1. 队伍按其队内编号最小的选手的编号进行排序。
2. 队伍编号是从 1 开始的连续整数。

例如，选手 {1}, {2, 3, 5}, {4, 6} 分成了三队。因为 min{1}=1, min{2,3,5}=2, min{4,6}=4，所以 {1} 是 1 号队，{2,3,5} 是 2 号队，{4,6} 是 3 号队。 这样，每个选手 i 都有一个对应的队伍编号 $a\_i$。上面的例子对应的序列是 1 2 2 3 2 3。

这个规则等价于一个简单的约束：第 i 名选手所属的队伍编号 $a\_i$ 不能超过 max(a_1, a_2, ..., a_{i-1}) + 1。

题目将所有可能的合法序列按字典序排序，并从 1 开始编号（天数）。我们的任务是，给定一个序列，求出它的排名（是第几天的方案）。

思路分析：从朴素 DFS 到 MLE#

这是一个经典的求字典序排名的问题，天然地指向了数位 DP 的思路。我们可以从高位到低位（即从第 1 个选手到第 $n$ 个）来确定排名。

一个序列 $A = (a_1, \dots, a_n)$ 的排名，等于 1 + (所有字典序小于 A 的合法序列 B 的数量)。

我们可以尝试用一个递归函数 dfs(pos, max_teams, is_limit) 来解决这个问题，其状态定义如下：

• pos: 当前正在考虑第 pos 个选手。
• max_teams: 在前 pos - 1 个选手中，已经出现过的最大队伍编号。
• is_limit: 一个布尔值，表示当前位的选择是否受到给定序列 A 的值的限制。

这个 dfs 函数可以用来计算在当前状态下，总共有多少种合法的方案。通过在主循环中枚举每一位，并计算当该位选择一个更小的值时后续有多少种方案，我们就能累加出总排名。

下面是一个基于此想法的 DFS 实现：

1
// 一个会导致 MLE (Memory Limit Exceeded) 的版本
2
vector dp(n + 1, vector<int>(n + 1, -1));
3

4
auto dfs = [&](auto &&self, int pos, bool limit, int maxn) -> int {
5
    if (pos == n) {
6
        return 1;
7
    }
8
    if (!limit && dp[pos][maxn] != -1) {
9
        return dp[pos][maxn];
10
    }
11
    int res = 0;
12
    // 当前选手可选的队伍编号上限
13
    int up = limit ? num[pos] : maxn + 1;
14
    for (int i = 1; i <= up; i++) {
15
        res = (res + self(self, pos + 1, limit && i == num[pos], max(i, maxn))) % M;
16
    }
17
    if (!limit) {
18
        dp[pos][maxn] = res;
19
    }
20
    return res;
21
};

局限性分析: 这个思路是正确的，但它的状态空间是 pos * maxn。pos 的范围是 $0 \dots n$，而 maxn 的范围也可以达到 $0 \dots n$。因此，DP 数组 的大小是 $O(n^2)$。当 $n=10000$ 时，$10000 \times 10000$ 的状态空间会轻易地超出内存限制（MLE）。

这启发我们，必须寻找一种更高效的 DP 状态设计和计算方法。

高效的排名 DP#

与其在外部循环计算排名，不如让 DP 本身直接计算排名。我们可以设计一个 DP 状态，它不仅包含方案数，还包含目标序列的排名。

状态定义 我们采用自底向上（从第 $n$ 个选手反向到第 1 个）的方式进行 DP，并使用滚动数组优化空间。

• dp[m][0]: 表示对于某个后缀的选手，在他们之前已经有 m 个队伍的情况下，总共有多少种合法的分配方案。
• dp[m][1]: 表示对于目标序列 A 的某个后缀，在他们之前已经有 m 个队伍的情况下，这个后缀序列在所有合法后缀中所处的排名。

状态转移 我们从第 i = n - 1 个选手开始，倒着计算到第 i = 0 个选手。在计算第 i 层的 DP 值时，我们会用到第 i + 1 层的结果。

1. dp[m][0] (方案数计算) 对于第 i 个选手，如果前面已经有 m 个队伍，他可以选择加入这 m 个队伍中的任意一个，或者新开一个 m + 1 号队伍。

   • 加入 m 个旧队伍：有 m 种选择。后续 n - i - 1 个选手面临的局面是，仍然有 m 个队伍可选。方案数为 m * dp_next[m][0]。
   • 新开 m + 1 号队伍：有 1 种选择。后续 n - i - 1 个选手面临的局面是，有 m + 1 个队伍可选。方案数为 1 * dp_next[m + 1][0]。 所以，转移方程为： dp[m][0] = m * dp_next[m][0] + dp_next[m + 1][0]

2. dp[m][1] (排名计算) 第 i 个选手的队伍是 a[i]。他的排名由两部分构成：

   • 贡献1: 第 i 位选择比 a[i] 小的队伍编号 k (1 <= k < a[i])，所能产生的所有后缀方案数。
   • 贡献2: 第 i 位选择 a[i]，然后看后缀 a[i+1...] 的排名。

   我们分两种情况讨论（基于 a[i] 是否是新队伍）：

   • Case 1: a[i] <= m (加入旧队伍)
     • 贡献1: 我们可以选择 k = 1, ..., a[i] - 1。这些选择都不会改变最大队伍数 m。因此，对于每一种选择，后续都有 dp_next[m][0] 种方案。总贡献为 (a[i] - 1) * dp_next[m][0]。
     • 贡献2: 我们选择了 a[i]，最大队伍数仍为 m。后续排名为 dp_next[m][1]。
     • 总排名: (a[i] - 1) * dp_next[m][0] + dp_next[m][1]。
   • Case 2: a[i] > m (新开队伍)
     • 根据合法性，此时必有 a[i] = m+1。
     • 贡献1: 我们可以选择加入旧的 m 个队伍。每种选择后续都有 dp_next[m][0] 种方案。总贡献为 m * dp_next[m][0]。
     • 贡献2: 我们选择了 a[i] = m+1，最大队伍数变为 m + 1。后续排名为 dp_next[m + 1][1]。
     • 总排名: m * dp_next[m][0] + dp_next[m + 1][1]。

代码实现#

这份代码完美地实现了上述思路，并通过滚动数组将空间复杂度优化到了 $O(n)$。

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4
constexpr int M = 1e6 + 7;
5

6
void solve() {
7
    int n;
8
    cin >> n;
9
    vector<int> a(n);
10
    for (int i = 0; i < n; i++) {
11
        cin >> a[i];
12
    }
13

14
    // dp[j][0] -> 方案数, dp[j][1] -> 排名
15
    // 状态 j 代表 max_teams + 1
16
    vector<array<int, 2>> dp(n + 2, {0, 0});
17

18
    // Base Case: 对于 0 个选手 (i=n), 方案数为1, 排名为1
19
    for (int j = 1; j <= n + 1; j++) {
20
        dp[j][1] = 1;
21
        dp[j][0] = 1;
22
    }
23

24
    // 从第 n-1 个选手倒推到第 0 个
25
    for (int i = n - 1; i >= 0; i--) {
26
        auto ndp = dp; // ndp 是 i 层的结果, dp 是 i+1 层的结果
27
        for (int j = 1; j <= n; j++) { // j 是 max_teams + 1
28
            int m = j - 1; // m 是 max_teams
29

30
            // 计算 ndp[j][0] (方案数)
31
            ndp[j][0] = (1LL * m * dp[j][0] % M + dp[j + 1][0]) % M;
32

33
            // 计算 ndp[j][1] (排名)
34
            if (a[i] <= m) { // Case 1: 加入旧队伍
35
                ndp[j][1] = (1LL * (a[i] - 1) * dp[j][0] % M + dp[j][1]) % M;
36
            } else { // Case 2: 新开队伍 (a[i] must be m+1)
37
                ndp[j][1] = (1LL * m * dp[j][0] % M + dp[j + 1][1]) % M;
38
            }
39
        }
40
        dp = std::move(ndp);
41
    }
42

43
    // 初始状态：0个选手之前，有0个队伍 (m=0), 对应 j=1
44
    cout << dp[1][1] << "\n";
45
}
46

47
int main() {
48
    ios::sync_with_stdio(false);
49
    cin.tie(nullptr);
50
    solve();
51
    return 0;
52
}

总结#

本题展示了数位 DP 的强大扩展性。当面对因为状态空间过大而无法直接实现的朴素 DP 时，我们可以尝试：

1. 优化 DP 目标: 从“计数”转为直接计算“排名”，将排名信息融入状态中。
2. 优化 DP 维度: 采用自底向上的递推，并结合滚动数组，将空间复杂度从 $O(n^2)$ 降至 $O(n)$，从而通过大规模数据。 这个从“计数”到“求排名”的思维转变，以及对 DP 状态和计算顺序的精妙设计，是解决复杂计数问题的关键。