记录编号	160626	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数字串拆分	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.881 s
提交时间	2015-04-29 07:48:55	内存使用	27.16 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int SIZEN=510;
const int MOD=998244353;
int timer=0;
class Matrix{
public:
	int n,m;
	int s[5][5];
	inline void clear(int n_,int m_){
		n=n_;
		m=m_;
		memset(s,0,sizeof(s));
	}
	inline void resize(int n_,int m_){
		n=n_;
		m=m_;
	}
	inline void unit(int x){
		n=m=x;
		memset(s,0,sizeof(s));
		for(int i=0;i<n;i++) s[i][i]=1;
	}
	inline void operator *= (const Matrix &b){
		static int c[5][5];
		LL now;
		int i,j,k;
		for(i=0;i<n;i++){
			for(j=0;j<b.m;j++){
				now=0;
				for(k=0;k<m;k++){
					now+=(LL)s[i][k]*b.s[k][j];
				}
				c[i][j]=now%MOD;
			}
		}
		memcpy(s,c,sizeof(s));
		m=b.m;
	}
};
void print(Matrix a){
	cout<<a.n<<" "<<a.m<<": "<<endl;
	for(int i=0;i<a.n;i++){
		for(int j=0;j<a.m;j++){
			cout<<a.s[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}
inline Matrix operator * (const Matrix &a,const Matrix &b){
	Matrix c;
	c.n=a.n,c.m=b.m;
	LL now;
	int i,j,k;
	for(i=0;i<c.n;i++){
		for(j=0;j<c.m;j++){
			now=0;
			for(k=0;k<a.m;k++){
				now+=(LL)a.s[i][k]*b.s[k][j];
			}
			c.s[i][j]=now%MOD;
		}
	}
	return c;
}
inline Matrix operator + (Matrix a,const Matrix &b){
	for(int i=0;i<a.n;i++){
		for(int j=0;j<a.m;j++){
			a.s[i][j]=(a.s[i][j]+b.s[i][j])%MOD;
		}
	}
	return a;
}
inline Matrix slowpow(Matrix a,int n){
	Matrix ans;
	ans.unit(a.n);
	for(int i=1;i<=n;i++) ans*=a;
	return ans;
}
inline Matrix quickpow(Matrix a,int n){
	Matrix ans;
	ans.unit(a.n);
	while(n){
		if(n&1) ans*=a;
		a*=a;
		n>>=1;
	}
	return ans;
}
char S[510];
int L,M;
Matrix step;
Matrix seq[SIZEN][SIZEN];
Matrix DP[SIZEN];
int F[SIZEN]={0};
void work(void){
	DP[0].unit(M);
	for(int i=1;i<=L;i++){
		DP[i].resize(M,M);
		for(int k=1;k<=i;k++){
			DP[i]=DP[i]+DP[i-k]*seq[i-k+1][i];
		}
	}
	F[0]=1;
	for(int i=1;i<=M;i++){
		for(int k=1;k<=M;k++){
			if(i-k<0) continue;
			F[i]=(F[i]+F[i-k])%MOD;
		}
	}
	Matrix ori;
	ori.clear(M,1);
	for(int i=0;i<M;i++) ori.s[i][0]=F[i];
	ori=DP[L]*ori;
	printf("%d\n",ori.s[0][0]);
}
Matrix step_pow[20];
void prepare(void){
	step.clear(M,M);
	for(int i=0;i<M-1;i++) step.s[i][i+1]=1;
	for(int i=0;i<M;i++) step.s[M-1][i]=1;
	step_pow[0].unit(M);
	for(int i=1;i<20;i++) step_pow[i]=step_pow[i-1]*step;
	for(int i=1;i<=L;i++){
		Matrix now;
		now.unit(M);
		for(int j=i;j<=L;j++){
			now=quickpow(now,10)*step_pow[S[j]-'0'];
			seq[i][j]=now;
		}
	}
}
void read(void){
	scanf("%s",S+1);
	L=strlen(S+1);
	scanf("%d",&M);
}
int main(){
	freopen("haoi2015_str.in","r",stdin);
	freopen("haoi2015_str.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}