#PQJ2759x15148. QOJ 2759_15148

    ID: 2866 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HAOI 2015字符串动态规划

QOJ 2759_15148

str(str.in | str.out | str.cpp) 时间限制:1S 空间限制:256MB 题目描述: 你有一个长度为n 的数字串。 定义f(S)为将S 拆分成若干个1~m 的数的和的方案数,比如m=2 时,f(4)=4,分别为 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 输出格式: 仅输出一个数表示答案 样例输入: 123 3 样例输出: 394608467 数据范围 对于30%的数据,字符串长度不超过5 对于60%的数据,字符串长度不超过18 对于100%的数据,字符串长度不超过500,m<=5