「HAOI2015」数字串拆分
定义 \(f_s\) 将 \(s\) 拆分成 \(1 \sim m\) 的数的和的方案数，\(g_s\) 将 \(s\) 这个数字串分割成若干个数字（允许前导 \(0\)），设它们的和为 \(x\)，那么 \(g_s=\sum f_x\)，输入 \(s\) 与 \(m\)，求 \(g_s\)。
我们可以发现 \(f_i\) 是非常好求的，\(f_i=\sum_{j=1}^m f_{i-j}\)，模拟一下可以发现这样是对的，那么转移矩阵也很简单了，下面以 \(m=5\) 作一个例子。
\[\begin{pmatrix} dp_i & dp_{i-1} & dp_{i-2} & dp_{i-3} & dp_{i-4} \end{pmatrix} \times \begin{pmatrix} 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 \end{pmatrix} = \begin{pmatrix} dp_{i+1} & dp_i & dp_{i-1} & dp_{i-2} & dp_{i-3} \end{pmatrix} \]令 \(s\) 在十进制下有 \(n\) 位，由于 \(n\) 太大，我们并不能暴力求出 \(g_s\)，记 \(F\) 为以上的转移矩阵，那么可以先预处理出 \(dp1_k={F^{10}}^{k-1}(1 \le k \le n)\)。
因为 \(f_1\) 始终为 \(1\)，所以很好得出 \(F^k=f_k\)。
那么令 \(dp2_i\) 为 \(s\) 中 \(1 \sim i\) 位构成的数的 \(g\) 的矩阵，\(dp3_{i,j}\) 为 \(s\) 中 \(i \sim j\) 位构成的数的 \(f\) 的矩阵。
则 \(dp2_i=dp3_1{1,i}+\sum_{j=1}^{i-1} dp2_j \times dp3_{j+1,i}\)，\(dp3_{i,j}=dp3_{i+1,j} \times {dp1_{j-i+1}}^{s_i}\)（\(s_i\) 为 \(s\) 从高到低位的第 \(i\) 位），当然 \(dp3\) 其实可以省略，我们可以在枚举 \(j\) 的时候直接求出来（具体看代码）。
对于 \(dp2\) 的式子，我们用样例来证明一下，因为矩阵 \(A^{x+y}=A^x \times A^y\) 并且拥有分配率的性质，那么可以得出下面式子：
\(dp2_1=f_1=dp3_{1,1}\)
\(dp2_2=f_{1+2}+f_{12}=f_1 \times f_2+f_{12}=dp2_1 \times dp3_{2,2}+dp3_{1,2}\)
\(dp2_3=f_{1+2+3}+f_{1+23}+f_{12+3}+f_{123}=f_1 \times f_2 \times f_3+f_1 \times f_{23}+f_{12} \times f_3+f_{123}\)
\(dp2_3=f_{123}+(f_1 \times f_2+f_{12})\times f_3+f_1 \times f_{23}=dp3_{1,3}+dp2_2 \times dp3_{3,3}+dp2_1 \times dp3_{2,3}\)
那么即使更长也是如此，证毕。
示例代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
char s[501];
struct matrix{
int m[6][6];
matrix(){
memset(m,0,sizeof(m));
}
matrix operator*(const matrix &a){
matrix b;
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
for(int l=0;l<k;l++) b.m[i][j]=(b.m[i][j]+1ll*m[i][l]*a.m[l][j])%998244353;
}
}
return b;
}
matrix operator+(const matrix &a){
matrix b;
for(int i=0;i<k;i++){
for(int j=0;j<k;j++) b.m[i][j]=(m[i][j]+a.m[i][j])%998244353;
}
return b;
}
}dp0,dp1[501],dp2[501];
matrix power(matrix ret,int b){
matrix ans;
for(int i=0;i<k;i++) ans.m[i][i]=1;
for(int i=0;i<b;i++) ans=ans*ret;
return ans;
}
int main(){
scanf("%s%d",s+1,&k);
n=strlen(s+1);
for(int i=0;i<k;i++) dp1[1].m[i][0]=1;
for(int i=1;i<k;i++) dp1[1].m[i-1][i]=1;
for(int i=2;i<=n;i++) dp1[i]=power(dp1[i-1],10);
for(int i=1;i<=n;i++){
dp0=power(dp1[1],s[i]-'0');
for(int j=i-1;j>=1;j--){
dp2[i]=dp2[i]+dp2[j]*dp0;
dp0=power(dp1[i-j+1],s[j]-'0')*dp0;
}
dp2[i]=dp2[i]+dp0;
}
printf("%lld",dp2[n].m[0][0]);
return 0;
}