🦊 数字串复原记-难
🐾 数字串复原记
（兔猫信奥学院 · 牛局长特别任务）
故事背景
今天，兔猫信奥学院迎来了来自哨兵城的贵客——牛局长携手豹警官、闪电、朱迪和尼克！ 他们带来了一段失真的测试日志：原本应该输出一个用空格分开的整数数组，结果由于打印程序忘记输出空格，屏幕只剩下一串连续数字。
“已知数组中的每个整数都位于 $[1,k]$，且任何数字段不允许出现前导 0。”
牛局长皱着眉头，对同学们发出指令：“请根据这两条规则，计算出有多少种切分方案能够还原出这串数字！答案要对 $10^9+7$ 取模。”
闪电（虽然动作慢）认真记录；尼克与朱迪跃跃欲试；豹警官忙着给大家发甜甜圈以补充体力。 这场 “数字串复原记” 由此展开……
题目描述
给定一串仅含数字的字符串 $s$（首位非 0）与一个整数上界 $k$。 将 $s$ 切分成若干连续片段，使得
- 每个片段代表的十进制整数 $x$ 满足 $1\le x\le k$；
- 任何片段若长度 $>1$ 时 不能以字符
'0'开头。
求满足条件的切分方案总数，结果对 $10^9+7$ 取模后输出。
输入格式
n
s
k
| 符号 | 含义 |
|---|---|
| $n$ | 字符串 $s$ 的长度 |
| $s$ | 仅由 0–9 组成、首位非 0 的数字串 |
| $k$ | 上界整数 |
输出格式
ans
ans 为可行切分方案数对 $10^9+7$ 取模后的结果。
样例
4
1000
10000
1
样例解释 1 唯一可行划分：$[1000]$；其值 $1000\le k$ 且无前导 0。
4
1000
10
0
样例解释 2 $k=10$ 太小。任何切分都会出现 $\gt10$ 或前导 0 的段，因此方案数为 0。
数据范围
- $1\le n\le10^{5}$
- $s$ 首位非 0，其他字符为
0–9 - $1\le k\le10^{9}$
提示
- 当 $k$ 的十进制位数为 $L$ 时，单个片段的长度至多为 $L$。
- 建议使用动态规划并滚动窗口统计，以获得 $O(n\cdot L)$ 时间复杂度、$O(n)$ 空间复杂度的解法。
任务就交给你们了！ 🐮✨🐆✨🐢✨🐰✨🦊 —— 兔猫信奥学院 & 哨兵城联合发布