题意
给出一个数字串 \(s_0\) 和一个数 \(m\)。
定义 \(f(n)\) 为把 \(n\) 拆分成若干个 \(1∼m\) 的数的和的方案数（有序）。
定义 \(g(n)\) 为将数字串 \(n\) 分成若干个数字（可以有前导 \(0\)），设祂们和为 \(x\)，则 \(g(n)\) 为所有情况下 \(f(x)\) 的和。
\(|s_0|\le500,1\le m\le5\)。
思路
显然，有 \(f(n)=\sum_{i=1}^mf(n-i)\)。可以用一个矩阵刻画。由于矩阵有分配律和结合律，可以记忆化搜索。记录当前到哪一位，当前这段数从哪里开始。每个位置有两种情况：把结束当前段和不结束当前段。复杂度为 \(\mathcal O(|s_0|^3m^3)\)。似乎承受不了。记录 \(F_{i,j}=f(s_0[i:j])\)，这个可以 \(\mathcal O(|s_0|^2m^3)\) 预处理，搜索时直接用 \(F\) 即可。
时间复杂度 \(\mathcal O(|s_0|^2m^3)\)。
代码
// Problem: P3176 [HAOI2015] 数字串拆分
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3176
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{int z;Modint(){z=0;}Modint(int x){x%=mod;z=x<0?x+mod:x;}Modint(long long x){x%=mod;z=x<0?x+mod:x;}Modint(short x){x%=mod;z=x<0?x+mod:x;}Modint(char x){x%=mod;z=x<0?x+mod:x;}Modint(bool x){x%=mod;z=x<0?x+mod:x;}friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}Modint operator-()const{return (Modint){-z};}Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}Modint&operator++(){z++,z%=mod;return *this;}Modint&operator--(){z--,z%=mod;return *this;}Modint operator++(int){Modint ls=*this;z++,z%=mod;return ls;}Modint operator--(int){Modint ls=*this;z--,z%=mod;return ls;}friend Modint ksm(Modint a,int b){Modint ans=1;while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}return ans;}friend void read(Modint&z){int x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();f?x=-x:0;z.z=x;}friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int mod=998244353,maxm=6,maxn=510;
#define M Modint<mod>
int n,m;
struct Matrix{M a[maxm][maxm];Matrix(){memset(a,0,sizeof(a));}Matrix operator*(const Matrix b)const{Matrix c;for(int i=1;i<=m;i++) for(int k=1;k<=m;k++) for(int j=1;j<=m;j++) c.a[i][j]+=a[i][k]*b.a[k][j];return c;}Matrix operator+(const Matrix b)const{Matrix c;for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) c.a[i][j]=a[i][j]+b.a[i][j];return c;}
};
Matrix fr[maxn][maxn],base,f[maxn][maxn];
string s;
bool flag[maxn][maxn];
Matrix dfs(int u,int lt){if(flag[u][lt]) return f[u][lt];if(u==1) return fr[u][lt];flag[u][lt]=1;Matrix ans;ans=ans+dfs(u-1,lt)+dfs(u-1,u-1)*fr[u][lt];return f[u][lt]=ans;
}
signed main(){read(s,m);for(int i=1;i<=m;i++) base.a[i][1]=1;for(int i=2;i<=m;i++) base.a[i-1][i]=1;n=s.size();s=" "+s;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) fr[i][i-1].a[j][j]=1;for(int j=i;j<=n;j++){fr[i][j]=fr[i][j-1];Matrix ls=fr[i][j];for(int c=1;c<=9;c++) fr[i][j]=fr[i][j]*ls;ls=base;for(int c=1;c<=s[j]-'0';c++) fr[i][j]=fr[i][j]*ls;}}Matrix ans=dfs(n,n);write(ans.a[1][1]);return 0;
}