Xếp Chồng Giấy

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Nông dân John viết $N$ chữ số trên các tờ giấy. Các con bò có hai số nguyên yêu thích $A$ và $B$ , và cần trả lời $Q$ truy vấn. Mỗi truy vấn cho khoảng $[l, r]$ , các con bò xử lý từng tờ giấy từ trái sang phải, với mỗi tờ có 3 lựa chọn:

Đặt lên đỉnh chồng giấy
Đặt xuống đáy chồng giấy
Bỏ qua tờ giấy

Sau đó đọc số từ đỉnh xuống đáy. Hãy đếm số cách chọn (trong $3^{r - l + 1}$ cách) tạo ra số nằm trong khoảng $[A, B]$ (modulo $10^{9} + 7$ ).

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $A$ , $B$ ( $1 \leq N \leq 300$ , $1 \leq A \leq B < 10^{18}$ ).
Dòng 2: $N$ chữ số $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 9$ ).
Dòng 3: Số nguyên $Q$ ( $1 \leq Q \leq 5 \cdot 10^{4}$ ).
$Q$ dòng tiếp theo: Hai số nguyên $l_{i}$ , $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq N$ ).

Dữ liệu ra

Với mỗi truy vấn, in số cách hợp lệ modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 300$
$1 \leq A \leq B < 10^{18}$
$1 \leq a_{i} \leq 9$
$1 \leq Q \leq 5 \cdot 10^{4}$

Ví dụ

Input	Output	Giải thích
5 13 327 1 2 3 4 5 3 1 2 1 3 2 5	2 18 34	Truy vấn 1: Từ chữ số [1,2], có 9 cách. Các số tạo được trong [13,327]: 12 và 21 (2 cách).

Bình luận

Không có bình luận tại thời điểm này.