记录编号	161031	评测结果	AAAAAAAAAA
题目名称	1966.[HAOI 2015]数字串拆分	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.142 s
提交时间	2015-04-30 18:24:17	内存使用	1.90 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod 998244353
#define maxn 510
using namespace std;
typedef long long LL;
struct Matrix
{
	LL digit[6][6];
	int n,m;
	friend Matrix operator * (const Matrix &a,const Matrix &b)
	{
		Matrix c;
		memset(c.digit,0,sizeof(c.digit));
		c.n=a.n,c.m=b.m;
		for(int i=1;i<=c.n;++i)
			for(int k=1;k<=a.m;++k)
				for(int j=1;j<=c.m;++j)
					c.digit[i][j]+=a.digit[i][k]*b.digit[k][j];
		for(int i=1;i<=c.n;++i)
			for(int j=1;j<=c.m;++j)
				c.digit[i][j]%=mod;
		return c;
	}
	void operator += (const Matrix &a)
	{
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
			{
				digit[i][j]+=a.digit[i][j];
				if(digit[i][j]>=mod)
					digit[i][j]-=mod;
			}
	}
}F[maxn],A,I,pw[maxn][10],now;
char a[maxn];
int m,n;
int Dp()
{
	A.n=A.m=I.n=I.m=m;
	for(int i=1;i<m;++i)
		A.digit[i+1][i]=1;
	for(int i=1;i<=m;++i)
		A.digit[i][m]=I.digit[i][i]=1;
	n=strlen(a+1);
	F[0]=pw[0][0]=I;
	for(int i=1;i<=9;++i)
		pw[0][i]=pw[0][i-1]*A;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=9;++j)
		{
			pw[i][j]=I;
			for(int k=1;k<=10;++k)
				pw[i][j]=pw[i][j]*pw[i-1][j];
		}
	for(int i=1;i<=n;++i)
	{
		now=pw[0][a[i]-'0'];
		F[i].n=F[i].m=m;
		for(int j=i-1;j>=0;--j)
		{
			F[i]+=now*F[j];
			if(j)
				now=now*pw[i-j][a[j]-'0'];
		}
	}
	return F[n].digit[m][m];
}
int main()
{
	freopen("haoi2015_str.in","r",stdin);
	freopen("haoi2015_str.out","w",stdout);
	scanf("%s %d",a+1,&m);
	printf("%d\n",Dp());
	fclose(stdin);
	fclose(stdout);
	return 0;  
}