当前位置:网站首页>CodeForces - 628D (数位dp)
CodeForces - 628D (数位dp)
2022-08-10 11:32:00 【51CTO】
Consider the decimal presentation of an integer. Let's call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.
For example, the numbers 1727374, 17, 1 are 7-magic but 77, 7, 123, 34, 71 are not 7-magic. On the other hand the number 7 is 0-magic, 123 is 2-magic, 34 is 4-magicand 71 is 1-magic.
Find the number of d-magic numbers in the segment [a, b] that are multiple of m. Because the answer can be very huge you should only find its value modulo 109 + 7 (so you should find the remainder after dividing by 109 + 7).
Input
The first line contains two integers m, d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — the parameters from the problem statement.
The second line contains positive integer a in decimal presentation (without leading zeroes).
The third line contains positive integer b in decimal presentation (without leading zeroes).
It is guaranteed that a ≤ b, the number of digits in a and b are the same and don't exceed 2000.
Output
Print the only integer a — the remainder after dividing by 109 + 7 of the number of d-magic numbers in segment [a, b] that are multiple of m.
Examples
Input
2 6 10 99
Output
8
Input
2 0 1 9
Output
4
Input
19 7 1000 9999
Output
6
题目大意:
求一个区间内某种数的个数,需要是m的倍数,并且奇数位不能包含d,偶数为必须包含d。数的位数是2000位。
思路:
首先是数位dp。
关于m的限制,直接便计算边取模就行。d限制,需要分奇偶讨论一下。
数的位数很大,需要用字符串,这样的话,闭区间,左边的数减一不好计算,需要特判一下。
代码:
边栏推荐
猜你喜欢
Go 事,Gopher 要学的数字类型,变量,常量,运算符 ,第2篇
个推数据资产管理经验 | 教你打造数据质量心电图,智能检测数据“心跳”异常
StoneDB 文档捉虫活动第一季
Network sockets (UDP and TCP programming)
If someone asks you about distributed transactions again, throw this to him
Can CLIP also do segmentation tasks?The University of Göttingen proposed a model CLIPSeg that uses text and image prompts to perform three segmentation tasks at the same time, draining CLIP capabiliti
常量及数据类型你还记得多少?
Nocalhost - Making development more efficient in the cloud-native era
时间序列的数据分析(五):简单预测法
VSCode远程连接服务器报错:Could not establish connection to “xxxxxx”的可能错误原因及解决
随机推荐
Can CLIP also do segmentation tasks?The University of Göttingen proposed a model CLIPSeg that uses text and image prompts to perform three segmentation tasks at the same time, draining CLIP capabiliti
微信小程序,全局变量一个地方改变了其他地方的状态也跟着改变。
嘉为蓝鲸荣获工信部“数字技术融合创新应用解决方案”
Licking Exercise - 63 Find all anagrams in a string
孩子自律性不够?猿辅导:计划表要注意“留白”给孩子更多掌控感
LeetCode 24. 两两交换链表中的节点
厚积薄发!安全狗再次获得科技成果转化认证!
7. Instant-ngp
An enhanced dynamic packet buffer management.论文核心部分
LeetCode 109. Sorted Linked List Conversion Binary Search Tree
Excel函数公式大全—LOOKUP函数
Configuration swagger
搜索--01
OPNsense安装配置Zenarmor
Not just running away, but saving the guy who mishandled rm -rf /*
力扣练习——64 最长和谐子序列
Introduction to Software Architecture
自媒体爆款标题怎么写?手把手教你写热门标题
力扣练习—— 矩形区域不超过 K 的最大数值和(hard)
有哪些好用的性能测试工具推荐?性能测试报告收费标准