记录编号	464470	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数字串拆分	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.727 s
提交时间	2017-10-25 20:25:47	内存使用	0.42 MiB

#include <cstdio>
#include <cstring>
#define mem(a,b) memset(a,b,sizeof(a))
inline void read(int& x)
{	char c=getchar();x=0;int y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x*=y;
}
typedef unsigned long long ull;
const int mod=998244353;
int m,n;
char T[505];
struct matrix
{	int s[6][6];
	matrix(){mem(s,0);}
	inline int *operator [](int x){return s[x];}
	inline void init(){mem(s,0);for(int i=0;i<m;++i) this->s[i][i]=1;}
	inline void pre()
	{	mem(s,0);for(int i=0;i<m;++i) this->s[i][0]=1;
		for(int i=0,j=m-1;i<j;++i) this->s[i][i+1]=1;
	}
	inline friend matrix operator *(matrix x,matrix y)
	{	matrix z;ull tmp;
		for(int i=0;i<m;++i)
			for(int j=0;j<m;++j)
			{	tmp=0;
				for(int k=0;k<m;++k) tmp+=1ll*x[i][k]*y[k][j];
				z[i][j]=tmp%mod;
			}
		return z;
	}
	inline friend matrix operator +(matrix x,matrix y)
	{	matrix z;
		for(int i=0;i<m;++i)
			for(int j=0;j<m;++j)
				z[i][j]=(1ll*x[i][j]+1ll*y[i][j])%mod;
		return z;
	}
}f[10][505],dp[505];
inline matrix qp(matrix x,int y)
{	matrix ans;ans.init();
	for(;y;y>>=1,x=x*x) if(y&1) ans=ans*x;
	return ans;
}
inline void init()
{	f[1][0].pre();f[0][0].init();
	for(int i=1;i<=n;++i) f[0][i].init(),f[1][i]=qp(f[1][i-1],10);
	for(int i=2;i<=9;++i) for(int j=0;j<=n;++j) f[i][j]=f[i-1][j]*f[1][j];
	dp[0].init();matrix now;
	for(int i=1;i<=n;++i)
	{	now=f[T[i]-'0'][0];
		for(int j=i-1;j>=0;--j)
		{	dp[i]=dp[i]+dp[j]*now;
			if(j) now=now*f[T[j]-'0'][i-j];
		}
	}
}
inline int solve()
{	freopen("haoi2015_str.in","r",stdin);
	freopen("haoi2015_str.out","w",stdout);
	scanf("%s",T+1);read(m);n=strlen(T+1);
	init();
	printf("%d",dp[n][0][0]);
	return 0;
}
int Anonymity=solve();
int main(){;}