地狱数位dp：圆滚滚的算术占卜_根

地狱数位 dp：圆滚滚的算术占卜

#3641. 「2021 集训队互测」圆滚滚的算术占卜

在具有高度智慧的、拥有“史莱姆的导师”之称的红头史莱姆的引导下，史莱姆们理解了十进制数，并能够利用数字进行占卜。

史莱姆每天会进行占卜活动，第 $k$ 天的流程如下：

1. 将 $n$ 的值设为 $k$。
2. 将 $n$ 的不含前导 0 的十进制表示写下来。如果现在已经写下来了一些数，就将 $n$ 写在它们的后面。
3. 令 $n := n - S(n)$，其中 $S(n)$ 表示 $n$ 的十进制表示的各位数字之和。例如，$S(233) = 2 + 3 + 3 = 8$，$S(114514) = 1 + 1 + 4 + 5 + 1 + 4 = 16$。
4. 如果 $n = 0$，结束占卜，否则回到第 2 步。

最终的占卜结果是一个十进制数字串。显然，它也表示了一个十进制数。史莱姆想让你帮它们求出，第 $L$ 天到第 $R$ 天的占卜结果之和是多少。由于答案可能很大，你只需要求出对 $998244353$ 取模后的结果。史莱姆们总共问了 $T$ 个这样的问题，你需要对每个问题求出答案。

$T\le 5\times 10^{4},1\le L\le R\le 10^{18}$。

阅前思考

神秘数位 $\rm dp$ 题。

我们当然要搞清楚这个过程在干什么，简单来说就是不断把 $n$ 拼接到答案最后，然后 $n\gets n-S(n)$，用转移表示就是：

$$f_n=f_{n-S(n)}+ng_{n-S(n)},g_n=10^{|n|}g_{n-S(n)}$$

显然这个过程中最特殊的部分是 $n\gets n-S(n)$，这构成了一棵树，对于很大的 $n$ 来说这个过程会持续很久，并且看起来没有什么规律。

虽然我们要求 $f$ 的前缀和，但我们连一项都不会求，考虑快速求 $f_n$。

过程长没什么优势，但是每步短有优势（步长至多是 $9\times 18=162$），我们需要为这个进程按照某种标准划分成若干阶段，使得两个阶段之间是可转移的。

由于步长短，我们得到了一个好性质：只需要记录倒数 $3$ 位是什么，以及高位的位数和，$n\gets n-S(n)$ 对高位的影响至多是 $1$（低位发生借位的时候），在转移中我们就可以动态维护 $S(n)$。

但是，对 高位 影响是 $1$ 并不一定对 高位和 影响是 $1$，借位的情况我们需要考虑，可这与知道高位的每个数又有什么区别呢？

考虑数位 $\rm dp$ 的核心特点：大多数情况是通用的，少数情况是特殊的，我们发现特殊的只有 $x0\to (x-1)9,x00\to(x-1)99,\cdots$，这些情况不过寥寥 $15$ 种。

卡住的点：$\rm dp$ 状态的设计不清，转移无从下手。

题解阅读

首先考虑 $L=R$，快速求 $f_n$。

想一想状态该如何设计？由于数位自动机的存在，高阶的数位 $\rm dp$ 题可以直接设计状态，而不必囿于原值（即状态中不应出现原值）。

根据上文思路的最后一点，我们似乎应该将 $x00000y$ 作为状态的设计点，正解与此相当类似，状态是 $(x+1)10^k+999-y$ 的形式（即 $x99999(999-y)$）。

称满足 $(x+1)10^k+999-y(k\ge 3)$ 形式的数是 $k$ 特殊数。

我们先理解正解的正确性，再来探索一下这么设的好处是什么。

虽然我们摸出了状态的形状，但原式中一个重要的问题没有解决：系数是带 $n$ 的，但我们记不下来 $n$。

定义 $k$ 特殊数的一次“转变”是不断操作直到 $x$ 这个部分发生借位，这个过程中所写下的数（以及其位数信息）我们称为 $g(k,x,y)$。

敏锐地注意到，$g(k,x,y)$ 对于位数和 $S(x)$ 相同的 $x$ 来说，其贡献是相同的一次函数。

这是一个极好的性质，状态的信息我们定为 $(k,b,t)$ 表示一次函数和 $10^{len}$。

同时，由于我们要维护数位自动机，还需维护 $f$ 表示这个过程对 $x$ 的差量，也就是 endnum-beginnum。

于是我们开始设状态 $S_{k,l,s,u,y}$，表示 $n=(x+1)10^k+999-y$，$x$ 最后一位是 $u$，前面还有 $l$ 位，前 $l$ 位的数位和是 $s$。

$S$ 表示状态组，包含 $k,b,t,f$。

（不理解可以把这个数的构成画出来。）

我们显然要利用之前的状态来转移，$k=3$ 的部分可以预处理出来。

转移，$S$ 表示状态组：

$$\begin{cases}S_{k,l,s,0,y}\gets S_{k-1,l+1,s,9,y}&u=0 \\S_{k,l,s,u,y}\gets S_{k-1,l+1,s,9,y}\otimes S_{k,l,s,u-1,y'}& u\in[1,9]\end{cases}$$

$S_1\otimes S_2$ 表示前一个状态组拼接上后一个状态组，当然这里的 $\gets$ 和 $\otimes$ 都是笼统含义，内部的每个量我们需要仔细推。

在那之前我们先来理解为什么这么转移，这是相当自然的：先后退一步，把 $9$ 让出来，然后利用状态本身减到 $9$ 发生借位。

注意第二个转移中有 $y'$，它指的是进行完第一个操作后的 $y$，它可以用旧 $y$ 和 $f$ 算出来。

然后是各状态的转移：$u=0$ 时显然 $f$ 不变，$(f,k,b,t)\gets(f,10k,9k+b,t)$，$(k,b)$ 的变换是因为后退一步导致了 $x\gets 10x+9$。

$u\ge 1$ 时，设 $S_{k-1,l+1,s,9,y}=(f,k,b,t),S_{k,l,s,u-1,y'}=(F,K,B,T)$，那么贡献是 $(f,10k,9k+b,t)\times (F,K,B-K,T)$，其中 $(f,k,b,t)\times(F,K,B,T)=(f+F,kT+K,bT+B,tT)$，也就是先写下第一部分再写下第二部分的贡献。

把 $9$ 让出来的贡献跟上面是一样的，减到 $9$ 发生借位这部分的贡献需要 $B'=B-K$ 的原因是：$k(x-1)+b=kx+(b-k)$。

求出了数位自动机后，我们注意到 $k=3$ 的特殊数很多，只需 $80$ 次即可跳到一个这种特殊数，然后我们就可以在数位自动机上跳了。

（$9$ 延伸到第一位的情况下，此时不能向高位借位，我们只能在第二位上跳。）

来分析复杂度，设 $w=18,b=10$。

由于总位数和是 $9$ 的倍数，实质上 $y$ 只有 $wb/b=w$ 个，在存储的时候我们可以压起来，用的时候解密。

所以预处理复杂度是 $w\times w\times wb\times b\times w=w^4b^2$，单次查询复杂度是 $wb$ 的（每位掉 $10$ 次）。

---

现在来看 $L\le R$ 的情况，要求区间和。

首先还是差分成前缀和，但我们一下子手足无措了。

结

为什么用 $9$ 做状态而不是 $0$？

最关键的一点是 $9$ 做状态时数位和是一个相对稳定的状态，而 $0$ 作状态时第一步就要引起突变。