当前位置:网站首页>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限制,需要分奇偶讨论一下。
数的位数很大,需要用字符串,这样的话,闭区间,左边的数减一不好计算,需要特判一下。
代码:
边栏推荐
- Interviewer: How are Dao, Service, Controller, Util, and Model divided in the project?
- Database management tool: dynamic read-write separation
- 【Untitled】
- 开源的作者,也有个生活问题
- LeetCode 25. K 个一组翻转链表
- OPNsense安装配置Zenarmor
- Samsung plans to start producing semiconductor components in Vietnam in 2023
- 微信小程序提交审核历史版本记录从哪里查看
- Intel pushes 20220809 CPU microcode update to patch Intel-SA-00657 security vulnerability
- Microchip launched a high-performance 77GHz millimeter-wave radar chip, and has received tens of thousands of orders before mass production
猜你喜欢
How to join We Media, learn about these 5 monetization modes, and make your account quickly monetize
ViT结构详解(附pytorch代码)
If someone asks you about distributed transactions again, throw this to him
Database management tool: dynamic read-write separation
Go 事,Gopher 要学的数字类型,变量,常量,运算符 ,第2篇
一文读懂NFT数字藏品为何风靡全球?
StoneDB 文档捉虫活动第一季
APP automation testing practice based on UiAutomator2+PageObject mode
mpf6_Time Series Data_quandl_correct kernel PCA_AIC_BIC_trend_log_return_seasonal_decompose_sARIMAx_ADFull
嘉为蓝鲸荣获工信部“数字技术融合创新应用解决方案”
随机推荐
一文详解 implementation api embed
codevs 2370 小机房的树 (LCA)
CLIP还能做分割任务?哥廷根大学提出一个使用文本和图像prompt,能同时作三个分割任务的模型CLIPSeg,榨干CLIP能力...
因为找不到lombok而找不到符号log
个推数据资产管理经验 | 教你打造数据质量心电图,智能检测数据“心跳”异常
HDU 6040 Hints of sd0061 (技巧)
Intel pushes 20220809 CPU microcode update to patch Intel-SA-00657 security vulnerability
Buckle Exercise - 61 Sort by frequency of characters
搜索--01
项目部署、
It is rumored that Samsung 3nm has won the second customer, and the current production capacity is in short supply
网络基础(第一节)
LeetCode 25. A set of K flipped linked lists
LeetCode 138. Copy a linked list with random pointers
LeetCode50天刷题计划(Day 18—— 搜索旋转排序数组(8.50-12.00)
LeetCode 19. Delete the Nth last node of the linked list
three.js模糊玻璃效果
LeetCode 369. Plus One Linked List(链表加1)
力扣练习——58 验证二叉搜索树
dedecms支持Word内容一键导入