Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
D. Шидэт тоонууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Хэрэв тухайн тоонд $d$ гэсэн цифр бүх тэгш байрлалууд дээр байх бөгөөд сондгой байрлалуудад байхгүй байвал уг тоог "$d$-шидэт" гэж нэрлэе.
Жишээлбэл $1727374$, $17$, $1$ гэсэн тоонууд нь "$7$-шидэт" тоонууд бөгөөд $77$, $7$, $123$, $34$, $71$ гэсэн тоонууд нь "$7$-шидэт" тоонууд биш юм. Өөрөөр хэлбэл $7$ бол "$0$-шидэт" тоо, $123$ бол "$2$-шидэт" тоо, $34$ бол "$4$-шидэт" тоо бөгөөд $71$ бол "$1$-шидэт" тоо юм.
Тэгвэл $[a, b]$ завсарт байх бөгөөд $m$ тоонд хуваагдах "$d$-шидэт" тоонуудын тоог олно уу. Хариулт нь маш том тоо гарч болох учраас хариултынхаа $(10^{9} + 7)$-д хуваасан үлдэгдлийг олно уу.
Оролт
Эхний мөрөнд өгөгдсөн нөхцлүүд болох бүхэл тоо $m, d$ өгөгдөнө. $(1 ≤ m ≤ 2000, 0 ≤ d ≤ 9)$
Хоёр дахь мөрөнд эерэг бүхэл $a$ тоо өгөгдөнө. Энэ тоо $0$-ээр эхлэхгүй.
Гурав дахь мөрөнд эерэг бүхэл $b$ тоо өгөгдөнө. Энэ тоо $0$-ээр эхлэхгүй.
$a ≤ b$ байх ба $a$ болон $b$ тоонууд нь ижил оронтой бөгөөд $2000$-аас хэтрэхгүй оронтой байна.
Гаралт
$[a, b]$ завсарт байх бөгөөд $m$ тоонд хуваагдах "$d$-шидэт" тоонуудын тоог $(10^{9} + 7)$-д хуваасан үлдэгдлийг хэвлэнэ үү.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
2 6 10 99
Гаралт
8
Оролт
2 0 1 9
Гаралт
4
Оролт
19 7 1000 9999
Гаралт
6
Тэмдэглэл
Эхний жишээний хариунд тоологдох тоонууд нь $16$, $26$, $36$, $46$, $56$, $76$, $86$, $96$ болох юм.
Хоёр дахь жишээний хариунд тоологдох тоонууд нь $2$, $4$, $6$, $8$ болох юм.
Гурав дахь жишээний хариунд тоологдох тоонууд нь $1767$, $2717$, $5757$, $6707$, $8797$, $9747$ болох юм.