题目描述
你有一个长度为n的数字串。定义f(S)为将S拆分成若干个1~m的数的和的方案数，比如m=2时，f(4)=5，分别为4=1+1+1+1你可以将这个数字串分割成若干个数字（允许前导0），将他们加起来，求f，并求和。比如g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)。已知字符串和m后求答案对998244353（7*17*223+1，一个质数）取模后的值。
输入输出格式
输入格式：
第一行输入一个字符串，第二行输入m
输出格式：
仅输出一个数表示答案
输入输出样例
说明
对于100%的数据，字符串长度不超过500，m<=5
先求出$f[s]$
显然$f[i]=\sum_{j=i-m}^{i-1}f[j]$
如果i特别大就可以用一个m*m的转移矩阵
也就是$(f_{i-m+1},f_{i-m+2},...f_{i})$的转移矩阵
预处理出A[i][j]表示数S为j*10^i的转移矩阵
对于$g$的转移：
显然$g[i]=\sum_{j=0}^{i-1}g[j]*D[j+1][i]$
$D[j+1][i]$表示j+1~i位构成的数的转移矩阵，显然可以通过A推出
g也要用一个矩阵表示
g[0]初始矩阵使$g_0=1$,也就是$(0,0,..,0,1)$
最后输出矩阵中代表$g_n$的方案，位置是(1,m)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int Mod=;
struct Matrix
{
int a[][];
}f[],A[][],now;
char s[];
int n,m,ans;
Matrix operator *(const Matrix &a,const Matrix &b)
{
int i,j,l;
Matrix res;
memset(res.a,,sizeof(res.a));
for (i=; i<=m; i++)
{
for (j=; j<=m; j++)
{
for (l=; l<=m; l++)
{
res.a[i][j]+=1ll*a.a[i][l]*b.a[l][j]%Mod;
if (res.a[i][j]>=Mod)
res.a[i][j]-=Mod;
}
}
}
return res;
}
Matrix operator +(const Matrix &a,const Matrix &b)
{
int i,j,l;
Matrix res;
memset(res.a,,sizeof(res.a));
for (i=; i<=m; i++)
{
for (j=; j<=m; j++)
{
res.a[i][j]=(a.a[i][j]+b.a[i][j])%Mod;
}
}
return res;
}
int main()
{int i,j;
cin>>s+;
n=strlen(s+);
cin>>m;
for (i=;i<=m;i++)
{
A[][].a[i][i]=;
}
for (i=;i<=m;i++)
{
A[][].a[i][m]=;
}
for (i=;i<m;i++)
{
A[][].a[i+][i]=;
}
for (i=;i<=;i++)
{
A[][i]=A[][i-]*A[][];
}
for (i=;i<=n;i++)
{
A[i][]=A[][];
A[i][]=A[i-][]*A[i-][];
for (j=;j<=;j++)
{
A[i][j]=A[i][j-]*A[i][];
}
}
f[].a[][m]=;
for (i=;i<=n;i++)
{
now=A[][s[i]-''];
for (j=i-;j>=;j--)
{
f[i]=f[i]+(f[j]*now);
if (j) now=A[i-j][s[j]-'']*now;
}
}
ans=f[n].a[][m];
cout<<ans;
}