这道题（LeetCode 3352）的核心思路是数位 DP 结合预处理约简次数。
关键观察：
– `s` 最长 800 位，所以一次置位约简后，数值最多不超过 800。
– 因此可以预处理 `ops[i]`：将 `i` 变成 1 需要多少次操作（1 \\le i \\le 800）。
– 问题转化为：统计小于 `n` 的正整数中，二进制中 1 的个数为 `setBits`，且 `ops[setBits] < k` 的数的个数。
数位 DP 设计：
– `dp(i, setBits, tight)`：处理到第 `i` 位，当前已有 `setBits` 个 1，`tight` 表示是否受 `s` 前缀限制。
– 若 `i == s.length()`，返回 `ops[setBits] < k && !tight`（必须严格小于 `n`）。
– 枚举当前位填 0 或 1（受 `tight` 限制），递归转移。
参考了 walkccc 的题解 和 Progiez 的 Java 实现，下面是可直接提交的 Java 实现：
```java
class Solution {
private static final int MOD = 1_000_000_007;
private int[] ops;
private String s;
private int k;
private Integer[][][] mem;
public int countKReducibleNumbers(String s, int k) {
this.s = s;
this.k = k;
this.ops = getOps(s);
this.mem = new Integer[s.length()][s.length() + 1][2];
// 统计 [1, n) 中 k-可约简的数，减去 0（0 不是正整数）
return count(0, 0, true) – 1;
}
// 返回从第 i 位开始，当前已有 setBits 个 1，tight 表示是否紧贴 s 前缀的方案数
private int count(int i, int setBits, boolean tight) {
if (i == s.length()) {
// 必须严格小于 n（!tight），且 ops[setBits] < k
return (ops[setBits] < k && !tight) ? 1 : 0;
}
if (mem[i][setBits][tight ? 1 : 0] != null) {
return mem[i][setBits][tight ? 1 : 0];
}
int res = 0;
int maxDigit = tight ? s.charAt(i) – '0' : 1;
for (int d = 0; d <= maxDigit; d++) {
boolean nextTight = tight && (d == maxDigit);
res += count(i + 1, setBits + d, nextTight);
if (res >= MOD) res -= MOD;
}
mem[i][setBits][tight ? 1 : 0] = res;
return res;
}
// 预处理：ops[i] 表示将 i 变成 1 需要的操作次数
private int[] getOps(String s) {
int n = s.length();
int[] ops = new int[n + 1];
for (int num = 2; num <= n; num++) {
ops[num] = 1 + ops[Integer.bitCount(num)];
}
return ops;
}
}
```
复杂度分析：
– 时间复杂度：O(n^2)，其中 n = \\text{s.length} \\le 800。状态数为 n \\times n \\times 2，每个状态转移 O(1)。
– 空间复杂度：O(n^2)，记忆化数组大小。
