记录编号	164068	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数字串拆分	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	2.338 s
提交时间	2015-05-27 21:45:46	内存使用	34.26 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int SIZEN=6;
const int L_N=500+10;
const int MOD=998244353;
struct Mat{
    int a[SIZEN][SIZEN];
    int n,m;
    Mat(){}
    Mat(int n,int m){
    	init(n,m);
    }
    void init(int n,int m,bool is_e=0){
        this->n=n, this->m=m;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
            a[i][j]=is_e && i==j;
        }
    }
    void init_e(int n){
        init(n,n,true);
    }
    Mat operator * (const Mat & b)const{
        Mat ret; ret.init(n,b.m);
        for(int i=1;i<=ret.n;i++){
            for(int j=1;j<=ret.m;j++){
            	LL tmp=0;
                for(int k=1;k<=m;k++){
                    tmp+=LL(a[i][k])*b.a[k][j];
                }
                ret.a[i][j]=tmp%MOD;
            }
        }
        return ret;
    }
    void operator += (const Mat & b){
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			a[i][j]=(a[i][j]+b.a[i][j])%MOD;
    		}
    	}
    }
    void print(){
    	printf("n=%d m=%d\n",n,m);
    	for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
    			printf("%d ",a[i][j]);
    		}
    		printf("\n");
    	}
    }
};

char str[L_N];
int N,M;
Mat f[L_N],pre[L_N][L_N],step_pow[10];

Mat power_slow(Mat & d,int k){
	Mat ret; ret.init_e(d.n);
	Mat tmp=d;
	while(k){
		if(k&1) ret=ret*tmp;
		tmp=tmp*tmp;
		k>>=1;
	}
	return ret;
}

Mat power(Mat & d,int k){
	Mat ret; ret.init_e(d.n);
	if(!k) return ret;
	ret=power(d,k/2);
	ret=ret*ret;
	if(k%2) ret=ret*d;
	return  ret;
}

int main(){
	freopen("haoi2015_str.in","r",stdin);
	freopen("haoi2015_str.out","w",stdout);
	scanf("%s",str+1);
	scanf("%d",&M);
	N=strlen(str+1);
	
	Mat STEP(M,M);
	for(int i=1;i<=M-1;i++){
		STEP.a[i][i+1]=1;
	}
	for(int i=1;i<=M;i++){
		STEP.a[M][i]=1;
	}
	step_pow[0].init_e(M);
	for(int i=1;i<=9;i++) step_pow[i]=step_pow[i-1]*STEP;
	
	for(int i=1;i<=N;i++){
		Mat num;
		num.init_e(M);
		for(int j=i;j<=N;j++){
			num=power(num,10)*step_pow[str[j]-'0'];
			//num=power(num,10)*power(STEP,str[j]-'0');
			pre[i][j]=num;
			//printf("pre[%d][%d]\n",i,j);
			//pre[i][j].print();
		}
	}
	
	//printf("QAQ\n");
	
	f[0].init_e(M);
	for(int i=1;i<=N;i++){
		f[i].init(M,M);
		for(int j=0;j<i;j++){
			f[i]+=f[j]*pre[j+1][i];
		}
		//printf("f[%d]\n",i);
		//f[i].print();
	}
	
	Mat BASE(M,1);
	int tf[10]={1};
	for(int i=1;i<=M-1;i++){
		for(int j=0;j<i;j++) tf[i]+=tf[j];
	}
	for(int i=1;i<=M;i++){
		BASE.a[i][1]=tf[i-1];
		//printf("tf[%d]=%d\n",i-1,tf[i-1]);
	}
	
	BASE=f[N]*BASE;
	int ans=BASE.a[1][1];
	printf("%d\n",ans);
	
	return 0;
}