题解

思路

设某个不充分数的编号为 $k$，在其末尾添加数字 $c$。当 $c<k\bmod11$ 时，新数仍不充分。比这个新数小的不充分数包括最初的九个一位数、编号小于 $k$ 的数的全部孩子，以及当前父亲的前 $c+1$ 个孩子。因此新编号为

$$9+\sum_{i=1}^{k-1}(i\bmod11)+c+1.$$

只关心编号模 $11$。完整的 $11$ 项余数和为 $55$，模 $11$ 为零，所以若 $r=k\bmod11$，转移为

$$\operatorname{next}(r,c)=\left(10+\frac{r(r-1)}2+c\right)\bmod11.$$

做法

子任务 1 按编号顺序生成所有不超过七位的“不充分数”，放入集合；再枚举字符串全部子串并查表。

子任务 2 枚举每个起点。首位非零时，初始编号余数就是该数字；向右逐位扩展，只要新数字小于当前余数就用上式更新余数并计数，否则停止。复杂度为平方级。

满分算法把相同余数的子串合并。令 cnt[r] 为上一个位置结尾、编号模 $11$ 为 $r$ 的合法子串数。读入新数字 $c$ 后，仅有 $r>c$ 的状态可以转移到 next(r,c)；若 $c>0$，还要加入以这一位开头的单数字子串，状态为 $c$。新状态总和累加进答案。

复杂度

子任务 1 的集合生成与查表规模只覆盖七位数；子任务 2 时间复杂度为 $O(|s|^2)$、空间复杂度为 $O(1)$；满分算法时间复杂度为 $O(11|s|)$、空间复杂度为 $O(11)$。

正确性证明

编号转移公式精确计算了所有更小不充分数的数量，因此 next 给出添加一位后新数的编号余数。对每个位置，满分 DP 的 11 个状态按编号余数无损划分了此前所有合法子串；条件 $c<r$ 与题目递归定义完全一致，且每个旧子串只产生唯一新子串。非零单字符子串单独加入，所有以当前位置结尾的合法子串恰被计数一次。对位置归纳后，累计和即全部合法子串出现次数。