#P6854. [2024年山东第二轮集训]三重数
[2024年山东第二轮集训]三重数
题目描述
给定一个正整数,把它写成不带前导零的十进制字符串。一次操作可以删除当前字符串中连续的三个相同字符。删除后,两侧的剩余字符直接拼接,后续仍按字符处理。
如果存在一组操作能删空字符串,则称这个正整数为三重数。例如 对应的字符串可以依次删除 333、111、000,最终为空。
给定正整数 ,求区间 中三重数的个数,对 取模。
输入格式
一行两个正整数 。
输出格式
一行一个整数,表示答案对 取模后的结果。
样例 1
6 998244353
261
样例 2
30 1000000007
142544351
样例 3
5000 998244353
541825357
数据范围
,,且 是质数。原题时间限制 秒,内存限制 MB。
| 测试点 | 上界 |
|---|---|
| 1–2 | 12 |
| 3–4 | 20 |
| 5–6 | 40 |
| 7–8 | 80 |
| 9–10 | 150 |
| 11–12 | 300 |
| 13–15 | |
| 16–18 | |
| 19 | |
| 20 |