数位 dp 进阶（数位自动机）

通常来说，我们遇到的数位 dp 都是在原状态上加上 $d,z,c$ 表示第 $d$ 位，是否顶格，本位选择的数。

也可以枚举计算数字与上界的 $lcp$ ，然后处理后面任意选的方案。

数位 $\rm dp$ 也可以与自动机结合，变得支持多组询问，我们不妨称其为数位自动机。

（瞎起的名字，这个 trick 如果有名字请务必联系我更正。）

CF924F Minimal Subset Difference

定义 $f(n)$ 表示将十进制数 $n$ 所有数码之间填入加号或者减号，最终得到的值的绝对值最小值。

$T$ 组询问，给定 $l, r, k$ ，求满足 $l \le m \le r$ 且 $f(m) \le k$ 的 $m$ 的个数。

数据范围： $1 \le T \le 5e4, 1 \le l \le r \le 1e18, 1 \le k \le 9$ 。

先考虑单组询问怎么做。

给定一个数字让你求那肯定直接 $\rm dp$ ， $f_i$ 表示绝对值集合是 $i$ 能否达到，简单搜一搜发现状态不是很多，只有大约 $10^4$ 种，于是你可以爆搜并建出自动机，然后搞一个 dp 套 dp。

多组询问，你发现 $k\le 9$ 很小，我们设 $g_{k,d,msk}$ 表示限制不超过 $k$ ，已经确定了 $[d,18]$ 位，当前状态是 $msk$ ，接下来所有情况的方案和。

预处理是容易的，求值的时候我们从高往低确定每一位，并枚举它的低位确加上答案，复杂度 $T*18*10$ ，可以通过预处理复杂度增加来省掉询问的一个 $10$ 。