Kimi k2.6 LeetCode 2999. 统计强大整数的数目 C++实现

以下是 LeetCode 2999. 统计强大整数的数目 的 C++ 实现，采用数位 DP（Digit DP）思路。

核心思路

强大整数的条件：
1. 后缀必须是 `s`
2. 每个数位都不超过 `limit`

利用容斥原理：`[start, finish]` 内的强大整数个数 = `[0, finish]` 内的个数 − `[0, start-1]` 内的个数。

C++ 代码

```cpp
class Solution {
public:
long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
this->s = s;
this->limit = limit;

// 计算 [0, start-1] 内的强大整数个数
t = to_string(start - 1);
memset(f, -1, sizeof(f));
long long a = dfs(0, true);

// 计算 [0, finish] 内的强大整数个数
t = to_string(finish);
memset(f, -1, sizeof(f));
long long b = dfs(0, true);

return b - a;
}

private:
string s; // 后缀
string t; // 当前上界数字的字符串
long long f[20]; // 记忆化数组，-1 表示未计算
int limit; // 数位上限

/**
* 数位 DP：计算小于等于 t 的强大整数个数
* @param pos 当前处理到的位置
* @param lim 是否受上界 t 的约束（tight）
*/
long long dfs(int pos, bool lim) {
// 如果上界 t 的长度比后缀 s 还短，不可能有以 s 为后缀的数
if (t.length() < s.length()) {
return 0;
}

// 不受 tight 约束时，可以用记忆化
if (!lim && f[pos] != -1) {
return f[pos];
}

// 到达后缀区域：剩余长度恰好等于 s 的长度
if (t.length() - pos == s.length()) {
// 如果受 tight 约束，需要判断后缀 s 是否 <= t 的剩余部分
return lim ? (s.compare(t.substr(pos)) <= 0 ? 1 : 0) : 1;
}

// 当前位可选的上限
int up = lim ? t[pos] - '0' : 9;
up = min(up, limit);

long long ans = 0;
for (int i = 0; i <= up; i++) {
// 继续递归下一位，更新 tight 状态
ans += dfs(pos + 1, lim && i == (t[pos] - '0'));
}

// 记忆化：只有不受 tight 约束时才存储
if (!lim) {
f[pos] = ans;
}
return ans;
}
};
```

关键点说明

要点 说明
容斥原理 `count(finish) - count(start-1)` 得到区间答案
后缀处理 当剩余长度等于 `s.length()` 时，进入强制匹配后缀的逻辑
tight 约束 `lim=true` 表示当前构造的前缀与上界 `t` 完全相同，下一位不能超过 `t` 的对应位
记忆化 只有 `lim=false`（不受 tight 约束）时才缓存结果，`lim=true` 时结果与具体上界相关
数位上限 每位可选 `0` 到 `min(limit, 上界对应位)`，同时满足 `limit` 和 `tight` 两个约束

复杂度分析

- 时间复杂度：O(\log M \times D)，其中 M 是数值上界（最大 10^{15}），D = 10 为可选数字个数。实际由于记忆化，状态数约为 O(\log M)。
- 空间复杂度：O(\log M)，用于记忆化数组和递归栈。