#P6854. [2024年山东第二轮集训]三重数

    ID: 6685 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-栈普通生成函数生成函数求系数Lagrange 反演组合数乘法递推逆元线性递推线性递推滚动数组对称性分析

[2024年山东第二轮集训]三重数

题目描述

给定一个正整数,把它写成不带前导零的十进制字符串。一次操作可以删除当前字符串中连续的三个相同字符。删除后,两侧的剩余字符直接拼接,后续仍按字符处理。

如果存在一组操作能删空字符串,则称这个正整数为三重数。例如 111003330111003330 对应的字符串可以依次删除 333、111、000,最终为空。

给定正整数 L,ML,M,求区间 [1,10L][1,10^L] 中三重数的个数,对 MM 取模。

输入格式

一行两个正整数 L,ML,M。

输出格式

一行一个整数,表示答案对 MM 取模后的结果。

样例 1

6 998244353
261

样例 2

30 1000000007
142544351

样例 3

5000 998244353
541825357

数据范围

1≤L≤1071\le L\le10^7,0.99×109≤M≤1.01×1090.99\times10^9\le M\le1.01\times10^9,且 MM 是质数。原题时间限制 11 秒,内存限制 512512 MB。

测试点 LL 上界
1–2 12
3–4 20
5–6 40
7–8 80
9–10 150
11–12 300
13–15 10310^3
16–18 10410^4
19 10610^6
20 10710^7

原 PDF 题面