神秘链接

首先发现 $f_i=\sum_{j=1}^m f_{i-j}$。

$m\le 5$，所以可以 $\mathcal{O(m^3\log n)}$ 计算 $f(n)$。

以 $m=3$ 为例：

$$\begin{bmatrix}f_n & f_{n-1} & f_{n-2}\end{bmatrix}\times \begin{bmatrix}1 & 1 & 0\\1 & 0 & 1\\1 & 0 & 0\end{bmatrix}=\begin{bmatrix}f_{n+1} & f_n & f_{n-1}\end{bmatrix}$$

撕烤如何计算 $g$。根据矩阵的结合律，先考虑转移矩阵的计算，最后再整体乘上初始矩阵。

考虑这样一个事实：$f(x+y)=G^{x+y}=G^x\times G^y=f(x)\times f(y)$，其中 $G$ 为转移矩阵。

基于此，可以 dp 求解原数字串的划分。

比如：$g(123)=g(12)\times f(3)+g(1)\times f(23)+f(123)$。

这样求解的前提是我们知道原串每个子段的 $f$ 值，这个可以递推求解。

设 $D_{i,j}=f(s_{i\sim j})$，则：

$$D_{i,j}=\begin{cases}f(s_i), & \mathrm{if}\ i=j\\f(s_i\times 10^{j-i})\times D_{i+1,j}, & \mathrm{Otherwise}\end{cases}$$

则有：

$$g_i=\sum_{j=0}^{i-1} g_j\times D_{j+1,i}$$

预处理 $D_{i,j}$ 之前先算出来 $f(c\times 10^k)$，时间复杂度可以做到 $\mathcal{O(n^2m^3)}$，我这里写少了，只处理了 $f(10^k)$，不过开 O2 也可以过。