题目名称	1966. [HAOI 2015]数字串拆分
输入输出	`haoi2015_str.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cstdio 于2015-04-27加入
开放分组	全部用户
提交状态
分类标签	动态规划矩阵运算 HAOI
查看题解	分享题解

通过：31，提交：66，通过率：46.97%
Asm.Def	100	0.593 s	5.59 MiB	C++
Anonymity	100	0.727 s	0.42 MiB	C++
张灵犀不和我一般见识真可怕呢（笑	100	0.819 s	38.09 MiB	C++
mikumikumi	100	0.819 s	38.09 MiB	C++
iortheir	100	0.857 s	1.39 MiB	C++
Asm.Def	100	1.142 s	1.90 MiB	C++
lbn187	100	1.345 s	0.76 MiB	C++
1	100	1.365 s	3.33 MiB	C++
Asm.Def	100	1.603 s	29.43 MiB	C++
yrtiop	100	1.651 s	54.57 MiB	C++

本题关联比赛
2022级数学专题练习赛1

关于数字串拆分的近10条评论(全部评论)
打表找规律摸了30 qwq CSU_Turkey 2017-10-25 21:15 11楼
星级诈骗.png..第一次"矩阵上的"DP... Anonymity 2017-10-25 20:28 10楼
才两星半？？ Rapiz 2017-03-24 21:20 9楼
求神犇讲讲怎么压掉那个log10的！ FoolMike 2016-11-22 20:14 8楼
卧槽...现在才写这题是不是没救了... （我大概能感受到夹心和萌帝考场上被卡常的心情了... Chenyao2333 2015-05-27 21:47 7楼
终于爆掉标程辣……QAQ 原来我之前写的预处理一直是$O(len^2 m^3 log 10)$的……怪不得慢这么多…… Asm.Def 2015-04-30 19:33 6楼
...终于过了...感谢神犇辅导了一个智障的我....... dydxh 2015-04-29 12:40 5楼
@Asm.Def : “有点”……呵呵呵呵呵呵呵呵呵呵 @dydxh 计算矩阵乘法时，用一个long long先存下所有a[i][k]*b[k][j]之和，然后统一取模 cstdio 2015-04-28 17:37 4楼
被常数卡成狗啊啊啊啊.....怎么过啊啊啊... dydxh 2015-04-28 17:31 3楼
“这题有点卡常数。”——YDC说道。这是唯一一道我在考场上能“想到做法”的题目（虽然没计算复杂度所以没加预处理……）顺便给题解打个广告：http://www.cnblogs.com/Asm-Definer/p/4466729.html Asm.Def 2015-04-28 00:16 2楼

1966. [HAOI 2015]数字串拆分

★★★ 输入文件：haoi2015_str.in 输出文件：haoi2015_str.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

你有一个长度为 $n$ 的数字串。

定义 $f(S)$ 为将 $S$ 拆分成若干个 $1 \sim m$ 的数的和的方案数，比如 $m=2$ 时，$f(4)=5$，分别为 $4=1+1+1+1， 4=1+1+2, 4=1+2+1， 4=2+1+1， 4=2+2$

你可以将这个数字串分割成若干个数字（允许前导 $0$），将它们加起来，求 $f$，并求和。

比如：$g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。

已知字符串和 $m$ 后求答案对 $998244353（7*17*223+1，一个质数）$取模后的值。

【输入格式】

第一行输入一个字符串，第二行输入 $m$。

【输出格式】

仅输出一个数表示答案。

【样例1输入】

123
3

【样例1输出】

394608467

【样例2输入输出】

点击下载样例2

【提示】

对于 $30\%$ 的数据，字符串长度不超过 $5$；

对于 $60\%$ 的数据，字符串长度不超过 $18$；

对于 $100\%$ 的数据，字符串长度不超过 $500，m \leq 5$。