大致题意： 定义(f(x))为将(x)分为若干在(1sim m)范围内的数之和（无序）的方案数，(g(s))为将(s)分割成若干段然后求和（设和为(x)）所有情况下(f(x))之和。
前言
第三次了。不知道为什么，同一个(C++)，试过别人的代码都可以调试，唯独我的代码就是会卡在调试界面无法调试。一定是我太弱了。。。
于是仅仅因为一个(j)不小心写成了(i)，大眼调试+输出调试搞了半天。
矩阵乘法
我似乎在很久以前写过一篇矩乘的博客，虽然可能比较水，姑且贴个链接吧：初学矩阵乘法。
要做这道题，矩阵乘法应该是不可或缺的（可以的话当我没说）。
显然，对于(f(x))，有：
[f(x)=sum_{i=1}^mf(x-i)
]
如果我们用一个(m imes 1)的矩阵，第(i)行表示(f(x-i))，则容易得到这样一个转移矩阵(seed)：
[egin{bmatrix}
0 & 1 & 0 & 0 & ... & 0\
0 & 0 & 1 & 0 & ... & 0\
0 & 0 & 0 & 1 & ... & 0\
... & ... & ... & ... & ... & ...\
0 & 0 & 0 & 0 & ... & 1\
1 & 1 & 1 & 1 & ... & 1
end{bmatrix}
]
即之前所有的(f(x-i))上移变成了(f(x-i-1))，而(f(x))是之前所有(f(x-i))的和。
动态规划
然后考虑怎么求(g(s))。
如果我们令(Ans(i))表示以(i)为结尾的答案矩阵之和（(m imes 1)的矩阵），(Trans(i,j))表示区间([i,j])对应数(t)的转移矩阵(seed^t)（(m imes m)的矩阵）。
那么我们就可以得到转移方程：
[Trans(i,j)=Trans(i,j-1)^{10} imes seed^{a_j}
]
[Ans(i)=sum_{j=0}^{i-1}Trans(j+1,i) imes Ans(j)
]
注意(Ans(i))中矩乘的顺序不能反。
则最终答案就是(Ans(n))第(m)行第(1)列的值。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500
#define M 5
#define X 998244353
#define XSum(x,y) ((x)+(y)>=X?(x)+(y)-X:(x)+(y))
using namespace std;
int n,m,a[N+5];string s;
struct Mat//矩阵
{
int n,m,a[M+5][M+5];I int *operator [] (CI x) {return a[x];}
I Mat(CI x=0,CI y=0):n(x),m(y){memset(a,0,sizeof(a));}
I Mat operator + (Con Mat& o) Con//矩阵加法
{
RI i,j;Mat t(n,m);for(i=1;i<=n;++i)
for(j=1;j<=m;++j) t[i][j]=XSum(a[i][j],o.a[i][j]);return t;
}
I Mat operator * (Con Mat& o) Con//矩阵乘法
{
RI i,j,k;Mat t(n,o.m);for(i=1;i<=n;++i) for(j=1;j<=m;++j)
for(k=1;k<=o.m;++k) t[i][k]=(1LL*a[i][j]*o.a[j][k]+t[i][k])%X;return t;
}
I Mat operator ^ (RI y) Con//矩阵快速幂
{
Mat x=*this,t(n,m);for(RI i=1;i<=n;++i) t[i][i]=1;
W(y) y&1&&(t=t*x,0),x=x*x,y>>=1;return t;
}
I void P()
{
for(RI i=1;i<=n;++i,putchar('
')) for(RI j=1;j<=m;++j) printf("%d ",a[i][j]);
}
}seed,pw[10],f[N+5],g[N+5][N+5];
int main()
{
RI i,j;for(cin>>s,n=s.length(),i=1;i<=n;++i) a[i]=s[i-1]&15;
for(scanf("%d",&m),seed=Mat(m,m),i=1;i^m;++i) seed[i][i+1]=seed[m][i]=1;seed[m][m]=1;//初始化转移矩阵
for(pw[0]=Mat(m,m),i=1;i<=m;++i) pw[0][i][i]=1;for(i=1;i<=9;++i) pw[i]=seed*pw[i-1];//初始化转移矩阵0~9的幂，方便后续转移
for(i=1;i<=n;++i) for(g[i][i]=pw[a[i]],j=i+1;j<=n;++j) g[i][j]=(g[i][j-1]^10)*pw[a[j]];//处理Trans矩阵
for(f[0]=Mat(m,1),f[0][m][1]=i=1;i<=n;++i)//枚举i
for(f[i]=Mat(m,1),j=0;j^i;++j) f[i]=f[i]+(g[j+1][i]*f[j]);//枚举先前一个j，求解Ans矩阵
return printf("%d",f[n][m][1]),0;//输出答案
}