题意重述

定义一个正整数 $x$ 是 $k$-美妙 的，如果可以将 $x$ 的十进制数码组成的可重集分成两个子集 $A$ 和 $B$，使得 $|\text{sum}(A) - \text{sum}(B)| \le k$。

给定 $n$ 个询问 $(l, r, k)$，求区间 $[l, r]$ 中 $k$-美妙 数的个数。

$1 \le n \le 5\times 10^4$，$1 \le l \le r \le 10^{18}$。

---

第一步：问题转化

$x$ 的数码可重集 $S$ 分成两个子集，和分别为 $s_A$ 和 $s_B$，则 $s_A + s_B = \text{sum}(S)$，差 $|s_A - s_B| = |\text{sum}(S) - 2s_B|$。

令 $t = s_B$，则差为 $|\text{sum}(S) - 2t|$，其中 $t$ 是某个子集的和。

要存在 $t$ 使 $|\text{sum}(S) - 2t| \le k$，等价于存在 $t$ 使：

$$\frac{\text{sum}(S) - k}{2} \le t \le \frac{\text{sum}(S) + k}{2}. $$

且 $t$ 必须是 $S$ 的某个子集和。

结论：$x$ 是 $k$-美妙的，当且仅当 $S$ 存在一个子集和 $t$ 满足上述不等式。

---

第二步：子集和的范围

子集和的范围是 $0$ 到 $\text{sum}(S)$ 之间的某些整数。

如果 $k \ge \text{sum}(S)$，那么显然总可以找到 $t$（比如 $t=0$ 或 $t=\text{sum}(S)$）使得差值 $\le k$（因为差最大是 $\text{sum}(S)$）。
但 $k \le 9$ 是固定的（样例中 $k$ 只到 $9$，题里没说 $k$ 范围，但从样例看 $k \le 9$），而 $\text{sum}(S)$ 可以很大（比如很多 $9$ 加起来），所以主要关心小 $k$ 情况。

---

关键观察

对于一个数码集合 $S$，能得到的子集和是连续的吗？
经典结论：如果 $S$ 中最大元素为 $m$，那么子集和能覆盖 $[0, \text{sum}(S)]$ 中的所有整数，当且仅当 $S$ 中所有元素和 $\le m + \sum_{i=0}^{m-1} i$ 的某个条件。
更简单地说：如果 $S$ 中最大的数不超过其余数之和加 $1$，则子集和是连续的。
实际上，如果我们将数码排序，$a_1 \le a_2 \le \dots \le a_d$，若 $\forall i, a_i \le 1 + \sum_{j=1}^{i-1} a_j$，则子集和是 $0$ 到 $\text{sum}(S)$ 的全部整数。

但这里数码是 $0\sim 9$，有可能不连续。不过对于本题 $k \le 9$（从数据范围看，通常 $k \le 9$），我们只需判断是否存在一个子集和 $t$ 落在 $\left[ \frac{\text{sum}(S)-k}{2}, \frac{\text{sum}(S)+k}{2} \right]$ 内。

由于 $k$ 很小，这个区间长度是 $k$，在 $\text{sum}(S)$ 很大时，只要子集和覆盖范围足够密，就很可能存在。

---

第三步：数位 DP 思路

我们需要统计 $[l, r]$ 中满足上述条件的 $x$ 的个数。
$r \le 10^{18}$，所以 $x$ 最多 $18$ 位十进制。

令 $f(pos, sum, mask, tight)$ 表示：

• 当前处理到第 $pos$ 位（从高到低）
• 当前已处理的数码总和为 $sum$
• $mask$ 表示 $0\sim 9$ 每个数码出现的奇偶性（或者更精确地，记录每个数码出现的次数 mod 2，因为子集划分只关心奇偶性？不，不能只记奇偶，因为可能一个数码出现多次）
• $tight$ 表示是否紧贴上界

这样状态数太大：$pos \le 18$，$sum \le 9\times 18 = 162$，$mask$ 要记录 $0\sim 9$ 每个数的个数（最多 $18$ 个），状态爆炸。

---

第四步：发现小 $k$ 的简化

因为 $k \le 9$，差值的限制很紧。
考虑两个子集和 $s_A, s_B$ 的差 $D = |s_A - s_B|$，显然 $D \equiv \text{sum}(S) \pmod{2}$（因为 $s_A+s_B=\text{sum}(S)$，所以 $D \equiv \text{sum}(S) \pmod{2}$）。

并且 $D$ 的最小可能值就是 $\text{sum}(S) \bmod 2$（如果 $\text{sum}(S)$ 是偶数，可以做到 $0$；奇数则至少 $1$）。

因此，如果 $k < (\text{sum}(S) \bmod 2)$，则不可能。
但 $k \ge 0$，所以奇数总和至少差 $1$，所以 $k=0$ 时只能选偶数总和的集合。

---

第五步：具体计算思路

对于固定 $x$，判断它是否是 $k$-美妙的：

设 $S$ 的数码总和为 $T$，我们看是否存在子集和 $t$ 满足 $\frac{T-k}{2} \le t \le \frac{T+k}{2}$。

等价于：是否存在 $t$ 使得 $|T-2t| \le k$，即 $t$ 靠近 $T/2$。

由于 $k$ 很小，我们只需检查 $t$ 能否取到 $\lfloor T/2 \rfloor$ 附近的几个值。
因为 $t$ 是整数，所以检查 $t = \lfloor T/2 \rfloor - m$ 到 $\lfloor T/2 \rfloor + m$ 的范围，其中 $m = \lceil k/2 \rceil$ 可能。

实际上更简单：
差 $|T-2t| \le k$ 意味着 $T-2t \in [-k, k]$，所以 $t \in \left[ \frac{T-k}{2}, \frac{T+k}{2} \right]$。

因为 $t$ 是整数，区间内整数个数最多 $k+1$ 个。

因此我们只需判断这个区间内是否有一个整数是 $S$ 的子集和。

---

第六步：数位DP设计

状态设计：
$dp[pos][sum][mask][tight]$，其中 $mask$ 用 $10$ 位二进制表示 $0\sim 9$ 数码的奇偶性？不行，需要具体个数。

由于 $k \le 9$，可能的 $T$ 在 $0$ 到 $162$ 之间。
对于给定 $T$，需要检查的 $t$ 区间长度 $\le 10$。
我们可以反过来枚举 $t$，然后判断 $S$ 是否有子集和等于 $t$。

但 $t$ 也有 $0$ 到 $162$ 的可能。

直接做子集和可行性判断：
在数位DP时，我们收集了所有数码的计数 $cnt[0..9]$，然后判断是否存在子集和 $t$ 在所需区间内。
这是一个 $0/1$ 背包可行性问题，但 $cnt[i] \le 18$，总和 $T \le 162$，可以在状态里存下可达到的子集和集合（bitset 长度 $163$）。

状态：$dp[pos][sum][bitset][tight]$，其中 $bitset$ 表示当前可达到的子集和集合。
但 $bitset$ 长度 $163$ 不能直接作状态维度。

---

第七步：观察优化

由于 $k \le 9$，我们不需要知道全部子集和，只需知道是否有一个子集和落在某个长度为 $k+1$ 的区间内。

定义 $can[delta]$ 表示是否存在子集和 $t$ 使得 $T-2t = delta$，即 $t = (T-delta)/2$ 是整数且可达。

因为 $delta \in [-k, k]$，所以只有 $2k+1$ 个可能的 $delta$ 值。
$delta$ 与 $T$ 奇偶性相同。

所以状态可以设计为： $dp[pos][sum][tight]$，同时维护一个 $2k+1$ 大小的布尔数组，表示在当前已选的数码集合下，对于当前总和 $T_{cur}$，可能的 $delta$ 是否存在。

但 $T_{cur}$ 随 $pos$ 增加变化，$delta$ 定义依赖于最终总和 $T$，我们不能预先知道 $T$。

---

第八步：另一种思路（数位DP+背包）

我们可以先枚举最终总和 $T$（$0$ 到 $9\times len$），然后做数位DP统计数码总和恰好为 $T$ 的数，同时检查是否 $k$-美妙。

检查 $k$-美妙的方法：
对数码集合做子集和DP（$0/1$ 背包），看是否存在 $t$ 满足 $|T-2t| \le k$。
这可以在数位DP时用 bitset 维护可达子集和集合，最后判断。

由于 $T \le 162$，bitset 长度 $163$，每个状态存一个 bitset 可行，但状态数：$pos \times T \times tight$ 约 $18\times 163\times 2 \approx 6000$，每个状态存 $163$ 位的 bitset（约 $21$ 字节），总内存约 $120KB$，可行。

---

状态定义： $dp[pos][sum][tight]$ 返回一个 bitset $bs$，其中 $bs[s] = 1$ 表示在当前已选的数码集合中，存在子集和为 $s$。

转移：
当前位选择数字 $d$，则新的 $sum' = sum + d$，新的 bitset $bs' = bs \ | \ (bs \ll d)$（因为加入数字 $d$ 后，所有原来的子集和 $s$ 可以变成 $s+d$）。

初始化：$bs[0] = 1$（空集和为 $0$）。

最终对于数 $x$，总和 $T$，bitset 为 $bs$，我们检查是否存在 $s$ 使 $|T-2s| \le k$，即检查 $s \in [\lceil (T-k)/2 \rceil, \lfloor (T+k)/2 \rfloor]$ 中是否有 $bs[s]=1$。

---

第九步：询问处理

有 $n$ 个询问，我们需要对每个 $(l, r, k)$ 计算 $[l, r]$ 中 $k$-美妙 数的个数。

如果每个询问单独做数位DP，$n \times$ 状态数 $\times$ 转移 会超时。

注意到 $k$ 只有 $0$ 到 $9$ 可能（从样例看），我们可以 预处理 所有 $k$ 的答案。

设 $F_k(x)$ 表示 $[0, x]$ 中 $k$-美妙 数的个数。
那么询问 $[l, r]$ 答案 = $F_k(r) - F_k(l-1)$。

我们对每个 $k = 0..9$，用数位DP计算 $F_k(x)$。
$x$ 最多 $10^{18}$，$18$ 位，状态 $dp[pos][sum][tight]$ 返回 bitset，记忆化。

由于 $k$ 很小，我们可以把 $k$ 也放进状态吗？不行，因为 $k$ 是询问参数，我们可以在数位DP结束后根据 $k$ 判断是否美妙。

更好的办法：
数位DP时不区分 $k$，只记录 $(sum, bitset)$，然后对于每个 $k$ 判断是否美妙，累加计数。

但这样要同时得到 $10$ 个 $k$ 的计数，状态返回时要返回一个数组 $cnt[k]$，表示在当前前缀下，继续填数能得到的 $k$-美妙 数个数。

---

最终方案： 记忆化搜索 $dfs(pos, sum, bs, tight)$ 返回一个数组 $ans[0..9]$，其中 $ans[k]$ 表示从当前状态继续填完剩余位，能得到 $k$-美妙 数的个数。

转移时枚举下一位数字，得到新的 $sum'$ 和 $bs'$，递归调用，把结果累加。

当 $pos = len$ 时，$sum = T$，$bs$ 是最终 bitset，我们对于每个 $k$ 判断是否存在 $s$ 使 $|T-2s| \le k$，是则 $ans[k] = 1$，否则 $0$。

---

第十步：复杂度

状态数：$pos \times sum \times tight$，约 $18 \times 163 \times 2 \approx 6000$，每个状态要返回 $10$ 个整数的数组，记忆化可行。

总复杂度：状态数 $\times$ 转移 $10$（数字选择） $\times$ $10$（$k$ 个数），约 $6000 \times 100 = 6\times 10^5$，再乘以询问数 $n$ 预处理后 $O(1)$ 回答，可以通过。

---

总结

本题的关键点：

1. 将 $k$-美妙 条件转化为子集和存在性问题。
2. 利用 $k \le 9$ 的小范围，只需检查长度为 $k+1$ 的区间。
3. 使用数位DP配合 bitset 维护子集和可行性。
4. 预处理所有 $k$ 的 $F_k(x)$，实现 $O(1)$ 回答询问。

这样就能在 $r \le 10^{18}$ 的大范围内高效处理多个询问。