题目概述

你有一个长度为 $n$ 的数字串。定义 $f(S)$ 为将 $S$ 拆分成若干个 $1\sim m$ 的数的和的方案数，你可以将这个数字串分割成若干个数字（允许前导 $0$），将他们加起来，求 $f$，并求和。

解题报告

很好的矩阵题，首先显然有 $f(i)=\sum_{k=1}^{m}f(i-k)$ ，所以我们可以构造一个转移矩阵 $T$ 。那么只要知道了 $f(i)$ ，就可以得出 $f(j)=f(i)\times T^{j-i}$ ，这样就可以快速求出 $f(a+b+c+d+\cdots)$ 。

想直接推出 $g(S)$ 是十分复杂的，我们可以考虑用矩阵表示出 $g(S)$ ，定义 $g[i]$ 表示 $S$ 前 $i$ 个字符的贡献矩阵，由于矩阵满足分配律，所以我们可以求出 $M[i][j]=T^{[i,j]\text{表示的数字}}$ ，枚举单独成段的数字，那么：

$$ g[i]=\sum_{j=0}^{i-1}g[j]M[j+1][i] $$

其含义就是在之前每种方案最后都加上了 $[j+1][i]$ 这一段，最后利用 $g[n]$ 求出答案即可。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=500,maxm=5,MOD=998244353;

int n,m,s[maxn+5];
struct Matrix{
    int r,c,s[maxm][maxm];
    void zero(int n,int m) {r=n;c=m;for (int i=0;i<n;i++) for (int j=0;j<m;j++) s[i][j]=0;}
    void unit(int n) {zero(n,n);for (int i=0;i<n;i++) s[i][i]=1;}
};
Matrix T,H[10],M[maxn+5][maxn+5],g[maxn+5];
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline Matrix operator + (const Matrix &a,const Matrix &b){
    static Matrix c;c.r=a.r;c.c=a.c;
    for (int i=0;i<a.r;i++)
        for (int j=0;j<a.c;j++)
            AMOD(c.s[i][j]=a.s[i][j],b.s[i][j]);
    return c;
}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero(a.r,b.c);
    for (int i=0;i<a.r;i++)
        for (int j=0;j<b.c;j++)
            for (int k=0;k<a.c;k++)
                AMOD(c.s[i][j],(LL)a.s[i][k]*b.s[k][j]%MOD);
    return c;
}

inline Matrix Pow(Matrix w,int b) {Matrix s;s.unit(m);while (b) {if (b&1) s=s*w;b>>=1;if (b) w=w*w;}return s;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (char ch=getchar();isdigit(ch);ch=getchar()) s[++n]=ch-48;scanf("%d",&m);
    T.zero(m,m);for (int i=0;i<m-1;i++) T.s[i+1][i]=1;for (int i=0;i<m;i++) T.s[i][m-1]=1;
    H[0].unit(m);for (int i=1;i<10;i++) H[i]=H[i-1]*T;
    for (int i=1;i<=n;i++)
        for (int j=(M[i][i]=H[s[i]],i+1);j<=n;j++)
            M[i][j]=Pow(M[i][j-1],10)*H[s[j]];
    g[0].unit(m);for (int i=1;i<=n;i++) g[i].zero(m,m);
    for (int i=1;i<=n;i++) for (int j=0;j<i;j++) g[i]=g[i]+g[j]*M[j+1][i];
    Matrix f;f.zero(1,m);int sum=f.s[0][0]=1;for (int i=1;i<m;i++) f.s[0][i]=sum,AMOD(sum,f.s[0][i]);
    return f=f*g[n],printf("%d\n",f.s[0][0]),0;
}