Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
E. Вэт Шарк ба Блокууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Цифрүүдээс бүрдэх $b$ блокууд байна. Блок бүр ижилхэн байх ба танд оролтонд өгөгдөх $n$ ширхэг тогтмол цифрүүдээс бүрдэнэ. Вэт Шарк блок бүрээс яг нэг цифр сонгох ёстой ба уг цифрүүдээ хооронд нь холбож нэг ширхэг бүхэл тоо үүсгэнэ. Жишээлбэл, хэрвээ тэр эхний блокоос $1$ цифрийг сонгож хоёр дахь блокоос $2$ гэсэн цифрийг сонгосон бол тэр $12$ гэсэн тоотой болно гэсэн үг.
Вэт Шарк уг тоог $x$ тоонд хуваагаад үлдэгдлийг авна. Түүнд $k$ тоог гарган авахын тулд блок бүрээс нэг цифрийг хэдэн янзаар авч болох вэ гэдгийг хэлж өгнө үү. Хариу болох тоо маш их байж болох учир уг тоог $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэ.
Нэг блокоос нэг цифрийг сонгох боломжийн тоо нь уг блокт уг цифр хэдэн ширхэг давтагдаж байгаа тоотой тэнцүү. Жишээлбэл, $3 5 6 7 8 9 5 1 1 1 1 5$ блокоос $5$ цифрийг сонгох боломжийн тоо $3$ юм.
Оролт
Оролтын эхний мөрөнд зайгаар тусгаарлагдсан дөрвөн бүхэл тоон утгууд $n$, $b$, $k$ ба $x$ ($2 ≤ n ≤ 50 000, 1 ≤ b ≤ 10^{9}, 0 ≤ k < x ≤ 100, x ≥ 2$) байх ба харгалзан нэг блок дахь цифрийн тоо, блокийн тоо, $x$-д хуваагаад гарах үлдэгдэл мөн $x$ өөрөө байна.
Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ 9$) байх ба блок бүрт байх цифрүүдийг өгч байгаа хэрэг юм.
Гаралт
$x$ тоонд хуваагаад гарах үлдэгдэл нь $k$-тай тэнцүү байх тоог блок бүрээс яг нэг цифр авах замаар хэдэн янзаар үүсгэж авч чадах боломжийн тоог хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
12 1 5 10 3 5 6 7 8 9 5 1 1 1 1 5
Гаралт
3
Оролт
3 2 1 2 6 2 2
Гаралт
0
Оролт
3 2 1 2 3 1 2
Гаралт
6
Тэмдэглэл
Хоёр дахь жишээн дээр боломжит бүхэл тоонууд нь $22$, $26$, $62$ ба $66$ байна. Эдгээрийн аль нь ч $2$-т хуваахад $1$ үлдэхгүй. In the second sample possible integers are $22$, $26$, $62$ and $66$. None of them gives the remainder $1$ modulo $2$.
Гурав дахь жишээн дээр боломжит бүхэл тоонууд нь $11$, $13$, $21$, $23$, $31$ ба $33$ байх ба бүгд $2$-т хуваахад $1$ үлдэнэ. Дээрх тоонуудыг гаргаж авах ганц ганц л боломж байгаа учраас нийт хариулт 6 байна.