HarmonyPairs - 题解

标签与难度

标签: 数位DP, 动态规划, 计数问题, 记忆化搜索, 组合数学

难度: 2000

题目大意喵~

喵哈~！各位算法爱好者们，今天我们来挑战一道有趣的计数题哦！

题目是这样的：给定一个非负整数 $N$ ，我们需要找出所有满足条件的数对 $(A, B)$ 的数量。这些数对需要满足三个条件：

$0 \le A \le B \le N$
$S(A) > S(B)$ ，其中 $S(x)$ 表示数字 $x$ 的各位数字之和。

因为 $N$ 可能会非常大（最多有100位！），所以我们不能简单地暴力枚举。最后的结果需要对 $10^9 + 7$ 取模，喵~

举个栗子，如果 $N=10$ ，那么数对 $(A, B)$ 就在 $[0, 10]$ 的范围内取。比如 $(A=7, B=10)$ 就是一个和谐对 (Harmony Pair)，因为 $A \le B$ 并且 $S(7)=7 > S(10)=1$ 。而 $(A=2, B=3)$ 就不是，因为 $S(2)=2 \le S(3)=3$ 。

我们的任务就是数清楚一共有多少这样可爱的和谐对啦！

解题思路分析

看到 $N$ 的范围这么大，我的胡须都警觉起来了！这通常意味着我们需要按位来处理，也就是经典的 数位DP 登场时间，喵！

这道题比普通的数位DP要复杂一点点，因为它涉及两个数 $A$ 和 $B$ 以及它们之间的关系。但别担心，基本思想是一样的：我们从高位到低位，一位一位地来确定 $A$ 和 $B$ 的数字，同时维护它们需要满足的约束条件。

让我们来想一想，在从左到右填充第 pos 位数字时，我们需要知道哪些信息才能做出决策，并且能够转移到下一个状态呢？

当前处理的位数 pos: 这是数位DP的必备参数，告诉我们现在决策到哪一位了。
$A$ 和 $B$ 的数位和之差 diff: 题目的核心条件是 $S(A) > S(B)$ 。我们可以在填充过程中，动态计算当前已填充部分 A_prefix 和 B_prefix 的数位和之差 S(A_prefix) - S(B_prefix)。我们把这个差值记为 diff。
$B$ 是否受 $N$ 的限制 is_N_limit: 为了保证 $B \le N$ ，我们在填充 $B$ 的第 pos 位时，能选择的数字会受到 $N$ 对应位上数字的限制。比如 $N = 857$ ，我们在填充百位时， $B$ 的百位最大只能是8。如果我们选了小于8的数字（比如7），那么 $B$ 后面就可以随便填了（0-9），这个限制就解除了。这个状态我们用一个布尔值 is_N_limit 来表示。
$A$ 是否受 $B$ 的限制 is_B_limit: 同理，为了保证 $A \le B$ ，在填充 $A$ 的第 pos 位时，能选择的数字也会受到 $B$ 对应位上数字的限制。这个状态我们用 is_B_limit 来表示。

有了这四个状态，我们就可以定义一个递归函数 dfs(pos, diff, is_N_limit, is_B_limit)，它表示：在当前状态下，继续填充完剩余位数，能构成和谐对的数量。

状态转移的细节

在 dfs(pos, diff, is_N_limit, is_B_limit) 中，我们需要做什么呢？

确定上界:
- $B$ 的当前位 digit_B 的上界 limit_B：如果 is_N_limit 为真，则 limit_B 是 $N$ 在 pos 位的数字；否则为9。
- $A$ 的当前位 digit_A 的上界 limit_A：如果 is_B_limit 为真，则 limit_A 是我们为 $B$ 选择的 digit_B；否则为9。

枚举与递归: 我们用两层循环来枚举所有可能的 digit_B 和 digit_A。

for digit_B from 0 to limit_B:
    for digit_A from 0 to limit_A:
        // 递归到下一位
        count += dfs(pos + 1, 
                     diff + digit_A - digit_B, 
                     new_is_N_limit, 
                     new_is_B_limit)

这里的 new_is_N_limit 和 new_is_B_limit 是根据当前选择的 digit_A 和 digit_B 更新的。

new_is_N_limit = is_N_limit AND (digit_B == limit_B)
new_is_B_limit = is_B_limit AND (digit_A == digit_B)

关于 diff: diff 的值可能是负数，但数组下标不能是负数呀！所以我们要给它一个偏移量 (OFFSET)。 $N$ 最多100位，每位最大数字是9。所以 $S(A)$ 和 $S(B)$ 最大都是 $9 \times 100 = 900$ 。diff 的范围大约是 $[-900, 900]$ 。我们取一个比如 OFFSET = 900，那么 diff 在数组中的索引就是 diff + OFFSET，就都是正数啦！
递归出口 (Base Case): 当 pos 遍历完所有位数时，我们就得到了完整的 $A$ 和 $B$ 。此时，我们检查最终的 diff。如果 diff > 0（也就是 $S(A) > S(B)$ ），说明我们找到了一个和谐对，返回1；否则返回0。
记忆化: 为了避免重复计算相同的子问题，我们用一个四维数组 dp[pos][diff + OFFSET][is_N_limit][is_B_limit] 来保存结果。这就是记忆化搜索，喵~

这样，通过从 dfs(0, OFFSET, true, true) 开始调用，我们就能算出最终的答案啦！

代码实现

下面是我根据上面的思路，精心重构的一份代码~ 注释很详细的，希望能帮到你理解，喵！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

// 定义一些常量，让代码更清晰~
const int MOD = 1e9 + 7;
const int MAX_LEN = 105; // N的长度最大为100
const int MAX_DIFF_SUM = 9 * MAX_LEN; // S(A)和S(B)的最大差值
const int OFFSET = MAX_DIFF_SUM; // 差值的偏移量，防止数组下标为负

// dp数组用于记忆化搜索
// dp[pos][diff][is_N_limit][is_B_limit]
long long dp[MAX_LEN][2 * MAX_DIFF_SUM + 5][2][2];

// N的字符串形式
string N_str;

/**
 * @brief 核心的DFS函数，用于数位DP
 * @param pos 当前处理的位数（从左到右，0-indexed）
 * @param diff 当前 S(A) - S(B) 的差值（已加上OFFSET）
 * @param is_N_limit B是否受到N的限制
 * @param is_B_limit A是否受到B的限制
 * @return 在当前状态下，能构成的和谐对的数量
 */
long long dfs(int pos, int diff, bool is_N_limit, bool is_B_limit) {
    // 递归出口：所有位都填完了
    if (pos == N_str.length()) {
        // 如果S(A) > S(B)，即 diff - OFFSET > 0，则找到一个有效对
        return diff > OFFSET ? 1 : 0;
    }

    // 检查记忆化数组，如果算过就直接返回，喵~
    if (dp[pos][diff][is_N_limit][is_B_limit] != -1) {
        return dp[pos][diff][is_N_limit][is_B_limit];
    }

    long long count = 0;
    
    // 确定B当前位的上界
    int limit_B = is_N_limit ? (N_str[pos] - '0') : 9;

    // 枚举B的当前位数字 digit_B
    for (int digit_B = 0; digit_B <= limit_B; ++digit_B) {
        // 确定A当前位的上界
        int limit_A = is_B_limit ? digit_B : 9;
        
        // 枚举A的当前位数字 digit_A
        for (int digit_A = 0; digit_A <= limit_A; ++digit_A) {
            // 准备递归到下一位
            // 更新is_N_limit: 只有当之前受限且当前位也取到上限时，下一位才继续受限
            bool next_is_N_limit = is_N_limit && (digit_B == limit_B);
            // 更新is_B_limit: 只有当之前受限且当前位也取到相等时，下一位才继续受限
            bool next_is_B_limit = is_B_limit && (digit_A == digit_B);

            // 累加结果
            count = (count + dfs(pos + 1, diff + digit_A - digit_B, next_is_N_limit, next_is_B_limit)) % MOD;
        }
    }

    // 将结果存入dp数组
    return dp[pos][diff][is_N_limit][is_B_limit] = count;
}

int main() {
    // 为了更快的输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N_str;

    // 初始化dp数组为-1，表示还未计算过
    memset(dp, -1, sizeof(dp));

    // 从第0位开始，初始差值为OFFSET，B和A都受限
    cout << dfs(0, OFFSET, true, true) << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(L^2 \times C^2)$ 我们的时间复杂度主要由DP状态的数量和每个状态的转移时间决定。
- 状态数量：pos 有 $L$ 种取值（ $L$ 是 $N$ 的长度，约100）。diff 的范围是 $[-9L, 9L]$ ，所以有约 $18L$ 种取值。两个布尔标志各有2种取值。总状态数约为 $L \times (18L) \times 2 \times 2 = O(L^2)$ 。
- 转移时间：在每个状态中，我们有两个嵌套循环，最多是 $10 \times 10 = 100$ 次。这个可以看作一个常数 $C^2$ （ $C=10$ ）。
- 所以总时间复杂度是 $O(L^2 \times C^2)$ 。对于 $L=100$ ，这是完全可以接受的。
空间复杂度: $O(L^2)$ 空间复杂度主要来自我们的记忆化数组 dp。其大小与状态数量相同，即 $O(L \times (18L) \times 2 \times 2) = O(L^2)$ 。

知识点总结

这道题是数位DP的一个非常好的练习，能帮助我们加深对DP思想的理解，喵~

数位DP (Digit DP): 解决与数字位有关的计数问题的通用框架。核心思想是按位构造数字，并用状态记录下所有影响后续决策的约束信息。
多变量DP: 与只处理一个数的数位DP不同，这里我们同时处理两个数 $A$ 和 $B$ 。关键在于将两个数的约束（ $A \le B, B \le N$ ）都融入到DP状态中。
状态设计: 正确设计DP状态是解题的关键。需要仔细分析题目条件，确保状态包含了所有必要信息，做到“无后效性”。
记忆化搜索: 使用递归配合数组（或哈希表）来记录子问题的解，是实现DP的一种直观且强大的方式。
偏移量技巧: 当状态中出现可能为负的整数时（比如本题的 diff），使用一个固定的偏移量将其映射到非负整数域，是处理数组下标的常用技巧。

希望这篇题解能让你对数位DP有更深的理解！如果还有问题，随时可以再来问我哦，喵~ >w<

HarmonyPairs - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

状态转移的细节 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​