题解

思路

一次操作对每一位独立生效，所以只需知道单个数字经过若干次操作后会产生多少位。数字尚未越过 $9$ 时只会加一；越过 $9$ 时会分裂为 $1$ 和 $0$，之后两部分继续独立演化。

令 $f_x$ 表示从数字 $0$ 开始连续增加 $x$ 次后得到的长度。当 $x<10$ 时长度为 $1$； 当 $x\ge10$ 时，第一次越过 $9$ 后产生的 $1$ 和 $0$ 分别还需演化 $x-10$ 次，因此可得到 $f_x=f_{x-9}+f_{x-10}$。

原数中的一位 $d$ 经过 $m$ 次操作，等价于数字 $0$ 经过 $m+d$ 次增加，所以其贡献为 $f_{m+d}$。

做法

预处理 $f_0$ 到 $f_{200009}$。对每组输入枚举 $n$ 的十进制数字，把每一位对应的 $f_{m+d}$ 相加并取模。

正确性证明

每次操作对各位分别替换，任何一位产生的新数字也只由这一位的后续演化决定，因此总长度等于 所有初始位贡献之和。

对单个初始数字，若总增量不足 $10$，它始终是一位，故初值正确。若总增量至少为 $10$，越过 $9$ 时恰好分裂为 $1$ 与 $0$；两部分剩余演化次数分别对应递推式中的 $f_{x-9}$ 与 $f_{x-10}$。由归纳法，递推值等于真实长度。于是逐位相加得到的就是整串最终长度。

复杂度

预处理时间复杂度为 $O(M)$，其中 $M=2\cdot10^5$。每组测试只枚举至多十个十进制位， 总时间复杂度为 $O(M+t\log n)$，空间复杂度为 $O(M)$。