题解

思路

处理一个普通序列时，令 $cnt_c$ 表示当前所有不同非空子序列中，以符号 $c$ 结尾的数量，并令

包含空序列。追加符号 $c$ 后，所有旧子序列都可以追加这个符号，因而新的 $cnt_c$ 恰为旧的 $T$，其他坐标不变。这是一个 $(k+1)$ 维向量的线性变换，最后一个坐标固定为 $1$。

另一方面，长度为 $k^m$ 的数位和模 $k$ 序列可以按最高位拆成 $k$ 个长度为 $k^{m-1}$ 的块；第 $d$ 块就是基础块的所有符号整体加 $d$ 再模 $k$。

做法

子任务 1：显式生成

逐个枚举 $j=0,1,\ldots,n-1$，计算其 $k$ 进制数位和模 $k$，再按上面的 $cnt$ 递推更新。时间 $O(n\log_k n)$，空间 $O(k)$。

子任务 2：朴素块矩阵

令 $A_{m,x}$ 表示长度为 $k^m$、所有符号整体增加 $x$ 的块对应的矩阵。$A_{0,x}$ 就是追加单个符号 $x$ 的矩阵。

从第 $m-1$ 层计算第 $m$ 层时，对每个偏移 $x$ 依次乘上 $k$ 个子块矩阵。这样每层需要 $k^2$ 次矩阵乘法，适合 $k\le8$。再按 $n$ 的 $k$ 进制前缀分解乘出长度为 $n$ 的矩阵。

子任务 3：前后缀积优化

对固定一层的 $A_{m-1,0},\ldots,A_{m-1,k-1}$，预处理块序列的所有前缀矩阵积 $P_x$ 和后缀矩阵积 $S_x$。偏移为 $x$ 的完整循环块由区间 $[x,k-1]$ 后接 $[0,x-1]$，所以只需一次矩阵乘法即可由 $P_x,S_x$ 得到 $A_{m,x}$。

每层由 $k^2$ 次矩阵乘法降为 $O(k)$ 次。最后递归处理长度 $n$ 的前缀：每层先合并若干完整子块，再进入唯一的残缺子块。

矩阵乘法的单个元素用 128 位整数累加后统一取模，避免 64 位累加溢出。

复杂度

• 子任务 1：时间 $O(n\log_k n)$，空间 $O(k)$。
• 子任务 2：时间 $O(k^5\log_k n)$，空间 $O(k^3\log_k n)$。
• 满分算法：时间 $O(k^4\log_k n)$，空间 $O(k^3\log_k n)$。