记录编号	354615	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数字串拆分	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.460 s
提交时间	2016-11-22 20:12:21	内存使用	50.00 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int p=998244353,N=510;
int n,m;char s[N];
struct matrix{
	ll a[5][5];
	matrix(){memset(a,0,sizeof a);}
	matrix operator * (const matrix &x){
		matrix ans;
		for (int i=0;i<m;i++)
		for (int j=0;j<m;j++){
			for (int k=0;k<m;k++)
				ans.a[i][j]+=a[i][k]*x.a[k][j];
			ans.a[i][j]%=p;
		}
		return ans;
	}
	void operator += (const matrix &x){
		for (int i=0;i<m;i++)
		for (int j=0;j<m;j++)
			a[i][j]=(a[i][j]+x.a[i][j])%p;
	}
}x,go[N][N],I,Mi_x[11];
matrix mi(matrix x){
	x=x*x;
	matrix ans=x;
	x=x*x;
	x=x*x;
	return ans*x;
}
ll arr[5]={1,1,2,4,8};
matrix dp[N];//dp[i]表示到达第i位的方案的矩阵之和 
int main()
{
	freopen("haoi2015_str.in","r",stdin);
	freopen("haoi2015_str.out","w",stdout);
	scanf("%s%d",s+1,&m);
	for (int i=0;i<m;i++) I.a[i][i]=1;
	for (int i=0;i<m-1;i++) x.a[i+1][i]=1;
	for (int i=0;i<m;i++) x.a[i][m-1]=1;
	Mi_x[0]=I;
	for (int k=1;k<=10;k++) Mi_x[k]=Mi_x[k-1]*x;
	n=strlen(s+1);
	for (int i=1;i<=n;i++) s[i]-='0';
	for (int i=1;i<=n;i++){
		go[i][i]=Mi_x[s[i]];
		for (int j=i+1;j<=n;j++)
			go[i][j]=mi(go[i][j-1])*Mi_x[s[j]];
	}
	memcpy(dp[0].a[0],arr,sizeof arr);
	for (int i=0;i<n;i++)
	for (int j=i+1;j<=n;j++)
		dp[j]+=dp[i]*go[i+1][j];
	printf("%lld\n",dp[n].a[0][0]);
	return 0;
}