C++14(g++5.4) 解法, 执行用时: 908ms, 内存消耗: 34144K, 提交时间: 2019-08-21 21:06:35

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN=505,MODE=998244353;
int m;

inline int add(int x,int y)
{
    return (x+=y)>=MODE?x-MODE:x;
}

struct Mat
{
    int lin, col,**a;
    Mat(int l = 0, int c = 0) : lin(l), col(c)
    {
        a = new int*[lin];
        for(int i = 0; i < lin; ++i) a[i] = new int[col]();
    }
    Mat(const Mat& x) // 拷贝构造函数
    {
        lin = x.lin, col = x.col;
        a = new int*[lin];
        for(int i = 0, j; i < lin; ++i)
            for(a[i] = new int[col], j = 0; j < col; ++j)
                a[i][j] = x[i][j];
    }
    ~Mat() // 析构函数
    {
        for(int i = 0; i < lin; ++i) delete[] a[i];
        delete[] a;
    }
    const int* operator[](int x) const { return a[x]; }
    int* operator[](int x) { return a[x]; }
    Mat& operator=(Mat x)
    {
        swap(a, x.a), swap(lin, x.lin), swap(col, x.col);
        return *this;
    }
    Mat operator*(const Mat& x) const // 带模矩阵乘法
    { // assert(col==x.lin);
        Mat ans(lin, x.col);
        for(int i = 0; i < lin; ++i)
            for(int j = 0; j < x.col; ++j)
                for(int k = 0; k < col; ++k)
                    ans[i][j] = add(ans[i][j], a[i][k] * (ll)x[k][j] % MODE);
        return ans;
    }
    Mat& operator*=(const Mat& x) { return *this = *this * x; }
    Mat& operator+=(const Mat& x)
    { // assert(lin==x.lin&&col==x.col);
        for(int i=0;i<lin;++i)
            for(int j=0;j<col;++j)
                a[i][j]=add(a[i][j],x[i][j]);
        return *this;
    }
    Mat operator^(ll ind) const // 快速幂
    { // assert(lin==col);
        Mat ans(lin, col), base(*this);
        for(int i = 0; i < lin; ++i) ans[i][i] = 1; // 单位阵
        for(; ind; base *= base, ind >>= 1)
            if(ind & 1) ans *= base;
        return ans;
    }
    void print() const
    {
        for(int i=0;i<lin||puts("");++i,puts(""))
            for(int j=0;j<col;++j) printf("%d ",a[i][j]);
    }
};

Mat dp[MAXN][MAXN],multi[10],ans[MAXN];
char str[MAXN];

int main()
{
    int m,L;
    scanf("%s %d",str,&m);
    L=strlen(str);
    Mat A(m,m);
    for(int i=0;i<m-1;++i) A[0][i]=A[i+1][i]=1;
    A[0][m-1]=1;
    multi[0]=A^0;
    for(int i=1;i<10;++i) multi[i]=multi[i-1]*A;
    for(int i=0;i<L;++i) dp[i][i]=multi[(int)str[i]-'0'];
    for(int i=0;i<L-1;++i)
        for(int j=i+1;j<L;++j)
            dp[i][j]=(dp[i][j-1]^10)*dp[j][j];
    for(int i=0;i<L;++i)
    {
        ans[i]=dp[0][i];
        for(int j=0;j<i;++j)
        {
            ans[i]+=ans[j]*dp[j+1][i];
        }
    }
    int sum=ans[L-1][0][0];
    printf("%d\n",sum);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 127ms, 内存消耗: 1128K, 提交时间: 2019-03-09 20:11:52

#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int N=1005,Mod=998244353;
int n,m,ch[N];
char st[N];
struct matrix{
    int A[6][6];
}f[15][N],g[N],tran;
matrix operator *(matrix a,matrix b){
    matrix res;
    memset(res.A,0,sizeof(res.A));
    for(int i=1;i<=m;i++)
        for(int k=1;k<=m;k++)
            if(a.A[i][k])
                for(int j=1;j<=m;j++){
                    res.A[i][j]=(res.A[i][j]+(ll)a.A[i][k]*b.A[k][j]%Mod);
                    if(res.A[i][j]>=Mod)res.A[i][j]-=Mod;
                }
    return res;
}
matrix operator +(matrix a,matrix b){
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++){
            a.A[i][j]+=b.A[i][j];
            if(a.A[i][j]>=Mod)a.A[i][j]-=Mod;
        }
    return a;
}
matrix fast_pow(matrix x,int e){
    matrix res=x;
    while(e){
        if(e&1)res=res*x;
        x=x*x;
        e>>=1;
    }
    return res;
}
int main(){
    scanf("%s",st+1);
    n=strlen(st+1);
    scanf("%d",&m);
    for(int i=1;i<=n;i++)ch[i]=st[i]-'0';
    for(int i=1;i<=m;i++){
        tran.A[i][m]=f[0][1].A[i][i]=1;
        if(i>1)tran.A[i][i-1]=1;
    }
    for(int i=1;i<=9;i++){
        f[i][1]=f[i-1][1]*tran;
        for(int j=2;j<=n;j++)
            f[i][j]=fast_pow(f[i][j-1],9);
    }
    g[0].A[1][m]=1;matrix tmp;
    for(int i=1;i<=n;i++){
        tmp=f[ch[i]][1];
        for(int j=i-1;j>=0;j--){
            g[i]=g[i]+g[j]*tmp;
            if (j && ch[j])tmp=tmp*f[ch[j]][i-j+1];
        }
    }
    printf("%d\n",g[n].A[1][m]);
    return 0;
}