题解

题中给的函数可以用矩阵快速幂递推

我们记一个数组dp[i]（这个数组每个元素是一个矩阵）表示从1到i所有的数字经过拆分矩阵递推的加和

转移方法是

\(dp[i] = \sum_{j = 0}^{i - 1} dp[j] * tr[j + 1][i]\)

\(tr[j][i]\)表示矩阵的\([j,i]\)组成的数字次幂是什么样的矩阵

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define MAXN 100005#define mo 994711//#define ivorysiusing namespace std;typedef long long int64;typedef long double db;typedef unsigned int u32;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {putchar('-');x = -x;}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}const int MOD = 998244353;int M,N;char s[505];int inc(int a,int b) {    return a + b >= MOD ? a + b - MOD : a + b;}int mul(int a,int b) {    return 1LL * a * b % MOD;}struct Matrix {    int f[6][6];    Matrix() {memset(f,0,sizeof(f));}    friend Matrix operator * (const Matrix &a,const Matrix &b) {    Matrix c;    for(int i = 0 ; i < M ; ++i) {        for(int j = 0 ; j < M ; ++j) {        for(int k = 0 ; k < M ; ++k) {            c.f[i][j] = inc(c.f[i][j],mul(a.f[i][k],b.f[k][j]));        }        }    }    return c;    }    friend Matrix operator + (const Matrix &a,const Matrix &b) {    Matrix c;    for(int i = 0 ; i < M ; ++i) {        for(int j = 0 ; j < M ; ++j) {        c.f[i][j] = inc(a.f[i][j],b.f[i][j]);        }    }    return c;    }}A[15],dp[505],tr[505][505];int g[15];Matrix fpow(Matrix x,int c) {    Matrix res = A[0],t = x;    while(c) {    if(c & 1) res = res * t;    t = t * t;    c >>= 1;    }    return res;}void Solve() {    scanf("%s",s + 1);    read(M);N = strlen(s + 1);    for(int i = 0 ; i < M ; ++i) {    A[0].f[i][i] = 1;    }    dp[0] = A[0];    g[0] = 1;    for(int i = 1 ; i < M ; ++i) {    for(int j = 1 ; j <= i ; ++j) {        g[i] = inc(g[i - j],g[i]);    }    }    for(int i = 0 ; i < M ; ++i) {    if(i != M - 1) A[1].f[i][i + 1] = 1;    A[1].f[M - 1][i] = 1;    }    for(int i = 2 ; i <= 9 ; ++i) {    A[i] = A[i - 1] * A[1];    }    for(int i = 1 ; i <= N ; ++i) {    Matrix r = A[0],t;    for(int j = i ; j <= N; ++j) {        r = r * r;t = r;        r = r * r;r = r * r;r = r * t;        r = r * A[s[j] - '0'];        tr[i][j] = r;    }    }    for(int i = 1 ; i <= N ; ++i) {    for(int j = 0 ; j < i ; ++j) {        dp[i] = dp[i] + dp[j] * tr[j + 1][i];    }    }    int ans = 0;    for(int i = 0 ; i < M ; ++i) ans = inc(ans,mul(g[i],dp[N].f[0][i]));    out(ans);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}