qwq真的是一道好题qwq自己做基本是必不可能做出来的。
首先，如果这个题目只是求一个(f)数组的话，那就是一道裸题。
首先，根据样例 根据题目描述，我们能发现其实同样数字的不同排列，也是属于不同的方案的，那统计起来其实方便很多。
首先我们发现，对于(i)这个数，他可以拆出来([1,m])任何一个数，接在对应的(f[i-1]到f[i-m])
也就是说(f[i]=f[i-1]+f[i-2]+f[i-3]....f[i-m])
qwq那我们可以构造出转移矩阵
以(m=3)为栗子
0 0 1
1 0 1
0 1 1
我们假设这个转移矩阵是(a)
那我们就可以直接将每一个(f[i])转化成，初始矩阵( imes a^i)的形式。
qwq但这个离我们求出来(g)数组还差好远。
由于(g)数组涉及(f)数组的拆分形式。
那我们不妨观察一下(f[i+j])等于多少。
那么我们就可以直接用矩阵乘法的形式来表示拼接了。
那g数组的转移式子，也就比较好求了
其中(d[j+1][i])表示([j+1,i])这些数从左到右排起来，组成的数的(f)的对应矩阵是多少。
这里转移式子的意义是，我们对于当前位，考虑枚举所有他的后缀，和前面任意的(f[i])的值乘起来，都是一个合法的方案（原理根据上面对(f[i+j])的讨论）。
之所以能直接用(g)数组来乘转移矩阵而不是一个一个分别乘。
是因为同大小的矩阵具有乘法分配律！
所以(g)也就可以直接和对应矩阵乘起来了
那么最后的(ans)，就应该是初始矩阵
还是以(m=3)为例
0 0 1
0 0 0
0 0 0
乘上(g[n])之后第一行最后一个元素的值，也就相当于(g[n])的第m行m列的那个元素。
现在整个问题的瓶颈到了怎么求(d)数组，由于数值太大，所以我们没有办法直接快速乘。
qwq
现在考虑递推
我们令(b[i][j])表示(i imes 10^j)的对应的f的转移矩阵是多少。
比较容易发现这个数组还是很好递推的。
每次(b[i][j]=qsm(b[i][j-1],10))
那知道这个数组，其实(d)数组也就不难推了
我们首先令(d[i][i]=b[s[i]-'0'][0])
那么(d[j][i]=d[j+1][i]*b[s[j]-'0'][i-j])
那么到这里这个问题也就基本解决了。
感觉细节真的是很多。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define mk make_pair
#define ll long long
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 7;
const int mod = 998244353;
struct Ju{
int x,y;
int a[maxn][maxn];
Ju operator * (Ju b)
{
Ju ans;
memset(ans.a,0,sizeof(ans.a));
ans.x=x;
ans.y=b.y;
for (int i=1;i<=ans.x;i++)
for (int j=1;j<=ans.y;j++)
for (int k=1;k<=y;k++)
ans.a[i][j]=(ans.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
return ans;
}
Ju operator +(Ju b)
{
Ju ans;
memcpy(ans.a,a,sizeof(ans.a));
ans.x=x;
ans.y=y;
for (int i=1;i<=x;i++)
for (int j=1;j<=y;j++)
ans.a[i][j]=(ans.a[i][j]+b.a[i][j])%mod;
return ans;
}
};
Ju qsm(Ju i,int j)
{
Ju ans;
memset(ans.a,0,sizeof(ans.a));
ans.x=i.x;
ans.y=i.y;
for (int p=1;p<=i.x;p++) ans.a[p][p]=1;
while (j)
{
if (j&1) ans=ans*i;
i=i*i;
j>>=1;
}
return ans;
}
char s[2020];
int n,m;
Ju a[510][510]; //a[i][j]表示，区间[i,j]的数的矩阵是多少
Ju ymh[510][510]; //ymh[i][j]表示,i*10^j的矩阵是多少
Ju lyf;
Ju g[510];//大小相同的矩阵乘法具有分配律
void init() //初始化矩阵的行和列
{
for (int i=0;i<=9;i++)
for (int j=0;j<=n;j++)
{
ymh[i][j].x=ymh[i][j].y=m;
}
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++)
{
a[i][j].x=a[i][j].y=m;
}
for (int i=0;i<=n;i++) g[i].x=g[i].y=m;
}
void print(Ju a)
{
cout<<"*******"<<endl;
cout<<a.x<<" "<<a.y<<endl;
for (int i=1;i<=a.x;i++)
{
for (int j=1;j<=a.y;j++)
cout<<a.a[i][j]<<" ";
cout<<endl;
}
}
signed main()
{
init();
scanf("%s",s+1);
m=read();
n=strlen(s+1);
init();
ymh[0][0].x=m;
ymh[0][0].y=m;
for (int i=1;i<=m;i++) ymh[0][0].a[i][i]=1; //设置初始矩阵
lyf.x=m;
lyf.y=m;
for (int i=1;i<m;i++) lyf.a[i+1][i]=1;
for (int i=1;i<=m;i++) lyf.a[i][m]=1; //设置转移矩阵
for (int i=1;i<=9;i++)
ymh[i][0]=ymh[i-1][0]*lyf; //先递推出来所有i*10^0的答案
for (int i=0;i<=9;i++)
for (int j=1;j<=n;j++)
ymh[i][j]=qsm(ymh[i][j-1],10); //预处理出来所有的值
// print(ymh[1][0]);
// print(ymh[0][0]);
for (int i=n;i>=1;i--)
{
a[i][i]=ymh[s[i]-'0'][0];
for (int j=i-1;j>=1;j--)
{
a[j][i]=ymh[s[j]-'0'][i-j]*a[j+1][i];
}
} //预处理a数组
//print(a[1][1]);
g[0]=ymh[0][0];
for (int i=1;i<=n;i++)
{
for (int j=i-1;j>=0;j--)
g[i]=g[i]+(g[j]*a[j+1][i]); //计算g，因为g是个sigma的数组，而且同大小矩阵乘法具有分配律，所以这句话表示，当前[j+1,i]这个串可以和之前任意一种组合，组合成一个串。
}
int ans=0;
//print(g[n]);
//for (int i=1;i<=m;i++) ans=(ans+g[n].a[1][i])%mod;
//cout<<ans<<endl;
cout<<g[n].a[m][m]<<endl;
return 0;
}