题解

思路

序列 $f$ 满足 $m$ 阶线性递推 $f(x)=\sum_{d=1}^m f(x-d)$。设其转移矩阵为 $T$，则一次切分中各段数值之和为 $x$ 时，贡献由 $T^x$ 决定。矩阵幂满足 $T^{x_1+\cdots+x_t}=T^{x_1}\cdots T^{x_t}$，因此可以直接对所有切分的矩阵幂求和。

做法

令 $D_i$ 为前 $i$ 个字符所有切分对应的 $T^{\text{段和}}$ 之和，$D_0=I$。若最后一段为 $s[j\ldots i-1]$，其十进制值为 $v$，则

从左到右扩展一个十进制数时，若旧值为 $v$、新数字为 $d$，则

部分分

当 $m=1$ 时恒有 $f(x)=1$，答案只等于切分数 $2^{|s|-1}$。当 $|s|\le15$ 时可以枚举所有切分。当 $|s|\le100$ 时可直接使用至多 $5\times5$ 的矩阵完成上述 DP。

商环优化

矩阵 $T$ 的特征关系为

因此任意 $T^v$ 都能唯一表示为次数小于 $m$ 的多项式。两个多项式相乘后，把每个 $X^d\ (d\ge m)$ 按上式从高次向低次消去即可。一次乘法只需 $O(m^2)$，而十次幂可由平方得到。

最终 $D_n=\sum_{t=0}^{m-1}c_tT^t$。预先计算 $f(0),\ldots,f(m-1)$，答案就是 $\sum c_tf(t)$。

正确性

每个切分有唯一的最后一段起点 $j$。归纳假设 $D_j$ 恰好包含前缀的全部切分，右乘最后一段的 $T^v$ 后指数相加，恰好得到完整切分的段和；对所有 $j$ 累加既无遗漏也无重复。商环化简只使用转移矩阵满足的特征关系，不改变矩阵值，因此最终线性函数给出的就是所有 $f(x)$ 之和。

复杂度

共有 $O(n^2)$ 个最后段转移，每次多项式运算为 $O(m^2)$，总时间复杂度 $O(n^2m^2)$，空间复杂度 $O(nm)$。