P3176 [HAOI2015] 数字串拆分
考虑 \(f\) 怎么求，由定义显然有 \(f(x)=\sum_{i=1}^m f(x-i)\)。
特别地，有 \(f(0)=1\)，\(f(i)=0,i<0\)。
这个转移可以用矩阵乘法刻画：
\[\begin{bmatrix}
1&1&1&\cdots&1&1\\
1&0&0&\cdots&0&0\\
0&1&0&\cdots&0&0\\
0&0&1&\cdots&0&0\\
\vdots&\vdots&\vdots&\ddots&0&0\\
0&0&0&\cdots&1&0
\end{bmatrix}
\times
\begin{bmatrix}
f_i\\f_{i-1}\\\vdots\\f_{i-m+1}
\end{bmatrix}
=
\begin{bmatrix}
\displaystyle\sum_{j=i-m+1}^i f_j\\
f_i\\\vdots\\f_{i-m+2}
\end{bmatrix}
=
\begin{bmatrix}
f_{i+1}\\f_i\\\vdots\\f_{i-m+2}
\end{bmatrix}
\]
记 \(\begin{bmatrix} f_i\\f_{i-1}\\\vdots\\f_{i-m+1} \end{bmatrix}\) 为 \(f(i)\) 对应的矩阵，\(s_{l\sim r}\) 表示数字串 \(s\) 中 \(l\sim r\) 位表示的数。
设 \(h_i\) 表示 \(g(s_{1\sim i})\) 的值，那么答案就是 \(h_{|s|}\)。
\(h_i\) 可以由 \(0\le j<i\) 的 \(h_j\) 转移而来，对于每个计入 \(h_j\) 的 \(f(x)\)，转移到 \(h_i\) 会让它们变成 \(f(x+s_{j+1\sim i})\)。相当于乘上转移矩阵的 \(s_{j+1\sim i}\) 次幂。
由于矩阵乘法具有乘法对加法的分配律，因此修改 \(h_i\) 的定义为所有会对 \(g(s_{1\sim i})\) 造成贡献的 \(f(x)\) 对应的矩阵之和。
记转移矩阵为 \(T\)，\(h_i\) 的转移为：
\[h_i=\sum_{j=0}^{i-1} h_j\times T^{s_{j+1\sim i}}
\]
其中 \(T^{s_{l\sim r}}\) 的式子可以预处理：
有 \(s_{l\sim r}=10s_{l\sim r-1}+s_r\)，因此
\[T^{s_{l\sim r}}\\ =T^{10s_{l\sim r-1}+s_r}\\ =(T^{s_{l\sim r-1}})^{10}\times T^{s_r} \]
可以递推求出。时间复杂度 \(\mathcal O(|s|^2m^3)\)。
#include<bits/stdc++.h>
#define N 505
using namespace std;
int n,m;char s[N];
constexpr int P=998244353;
struct Mat{int a[5][5];Mat(){memset(a,0,sizeof a);}void operator+=(const Mat &x){for(int i=0;i<m;i++) for(int j=0;j<m;j++)(a[i][j]+=x.a[i][j])<P||(a[i][j]-=P);}Mat operator*(const Mat &x){Mat res;for(int i=0;i<m;i++)for(int j=0;j<m;j++){long long v=0;for(int k=0;k<m;k++)v+=1ll*a[i][k]*x.a[k][j];res.a[i][j]=v%P;}return res;}
}f[N],g[N][N],T[10];
Mat Pow(const Mat &x){Mat res=x;for(int i=0;i<9;i++)res=res*x;return res;
}
int main(){scanf("%s%d",s+1,&m);n=strlen(s+1),f[0].a[0][0]=1;for(int i=0;i<m;i++){T[0].a[i][i]=T[1].a[0][i]=1;if(i<m-1) T[1].a[i+1][i]=1;}for(int i=2;i<=9;i++) T[i]=T[i-1]*T[1];for(int i=1;i<=n;i++){g[i][i]=T[s[i]^48];for(int j=i+1;j<=n;j++)g[i][j]=Pow(g[i][j-1])*T[s[j]^48];}for(int i=1;i<=n;i++)for(int j=0;j<i;j++)f[i]+=f[j]*g[j+1][i];printf("%d",f[n].a[0][0]);return 0;
}