记录编号	577976	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数字串拆分	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	1.651 s
提交时间	2023-01-03 18:43:53	内存使用	54.57 MiB

// Problem: P3176 [HAOI2015]数字串拆分
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3176
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using i64 = long long;

const int maxn = 505;
const int maxm = 5;
const i64 mod = 998244353;
int n,m;
char s[maxn];

struct matrix {
	i64 g[maxm][maxm];
	matrix() {
		memset(g , 0 , sizeof(g));
	}
	void clear() {
		memset(g , 0 , sizeof(g));
		return ;
	}
	void init() {
		for(int i = 0;i < m;++ i)
			g[i][i] = 1;
		return ;
	}
	void output() {
		puts("TEST:");
		for(int i = 0;i < m;++ i) {
			for(int j = 0;j < m;++ j)
				printf("%lld ",g[i][j]);
			puts("");
		}
		return ;
	}
	matrix operator * (const matrix& p)const {
		matrix c;
		for(int k = 0;k < m;++ k)
			for(int i = 0;i < m;++ i)
				for(int j = 0;j < m;++ j)
					(c.g[i][j] += g[i][k] * p.g[k][j] % mod) %= mod;
		return c;
	}
	matrix operator + (const matrix& p)const {
		matrix c;
		for(int i = 0;i < m;++ i)
			for(int j = 0;j < m;++ j)
				c.g[i][j] = (g[i][j] + p.g[i][j]) % mod;
		return c;
	}
}f,g[maxn],pw[maxn],d[maxn][maxn];

matrix power(matrix x,int y) {
	matrix ans;
	ans.init();
	for(;y;y >>= 1) {
		if(y & 1)ans = ans * x;
		x = x * x;
	}
	return ans;
}

int main() {
	freopen("haoi2015_str.in","r",stdin);
	freopen("haoi2015_str.out","w",stdout);
	scanf("%s %d",s + 1,&m);
	n = strlen(s + 1);
	for(int i = 1;i <= n;++ i)
		s[i] ^= '0';
	for(int i = 1;i < m;++ i)
		pw[0].g[i - 1][i] = 1;
	for(int i = 0;i < m;++ i)
		pw[0].g[i][0] = 1;
	f.g[0][0] = 1;
	for(int i = 1;i < n;++ i)
		pw[i] = power(pw[i - 1] , 10);
	for(int j = 1;j <= n;++ j)
		for(int i = j;i;-- i) {
			if(i == j)
				d[i][j] = power(pw[0] , s[i]);
			else
				d[i][j] = power(pw[j - i] , s[i]) * d[i + 1][j];
		}
	for(int i = 1;i <= n;++ i) {
		g[i] = d[1][i];
		for(int j = i - 1;j;-- j)
			g[i] = g[i] + g[j] * d[j + 1][i];
	}
	printf("%lld\n",(f * g[n]).g[0][0]);
	return 0;
}