拆分的情况下，发现f数组本身并不是很好递推。
因为f(123)=f(123)/f(12+3)/f(1+2+3)。
然后考虑f可以怎么表示f(n)=a0*M^n M为转移矩阵。
然后发现 f(x+y)=a0*M(x+y)， 所以只需要对M矩阵进行DP即可。
这样子每一个位置就可以表示为若干转移矩阵的和，然后就可以利用矩阵的相乘进行递推。
最后直接用原向量乘上转移矩阵即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define ll long long
#define F(i,j,k) for (ll i=j;i<=k;++i)
#define D(i,j,k) for (ll i=j;i>=k;--i)
const ll md=998244353; ll m,l;char s[505]; struct matrix{
ll x[6][6];
void init(){memset(x,0,sizeof x);}
void build1(){
init();
x[1][1]=1;
}
void build2(){
init();
F(i,1,m) x[i][1]=1;
F(i,1,m-1) x[i][i+1]=1;
}
void build3(){
init();
F(i,1,m) x[i][i]=1;
}
matrix operator * (matrix b) {
matrix ret;
ret.init();
F(i,1,m) F(j,1,m)
{
F(k,1,m)
ret.x[i][j]=ret.x[i][j]+x[i][k]*b.x[k][j];
ret.x[i][j]%=md;
}
return ret;
}
matrix operator + (matrix b) {
matrix ret;
ret.init();
F(i,1,m) F(j,1,m)
ret.x[i][j]=((ll)x[i][j]+(ll)b.x[i][j])%md;
return ret;
}
}dp[505],one,c[11][501],turn,now,ans; int main()
{
scanf("%s",s+1);l=strlen(s+1);
scanf("%lld",&m);
F(i,0,l) dp[i].init();
one.build1();
turn.build2();
c[0][0].build3();
F(i,1,10) c[i][0]=c[i-1][0]*turn;
F(i,1,l-1)
{
c[0][i]=c[0][i-1];
c[1][i]=c[10][i-1];
F(j,2,10)
{
c[j][i]=c[j-1][i]*c[10][i-1];
}
}
dp[0].build3();
F(i,1,l)
{
now.build3();
D(j,i,1)
{
now=now*c[s[j]-'0'][i-j];
dp[i]=dp[i]+dp[j-1]*now;
}
}
ans=dp[l]*one;
printf("%lld\n",ans.x[1][1]);
}