Khối chữ số modulo

Điểm: 7,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

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho $b$ khối, mỗi khối chứa cùng $n$ chữ số (nằm trong khoảng $1$ đến $9$ ) được cho trong dữ liệu vào.

Bạn phải chọn đúng một chữ số từ mỗi khối, rồi ghép các chữ số đã chọn theo thứ tự khối thành một số nguyên lớn. Hãy đếm số cách chọn sao cho số nguyên thu được chia $x$ dư đúng $k$ . Vì kết quả có thể rất lớn, hãy in nó theo modulo $10^{9} + 7$ .

Hai cách chọn được coi là khác nhau nếu tại một khối nào đó, vị trí của chữ số được chọn trong khối là khác nhau (kể cả khi giá trị của chữ số trùng nhau). Ví dụ, khối $3 5 6 7 8 9 5 1 1 1 1 5$ có ba cách chọn chữ số $5$ (vì chữ số $5$ xuất hiện ba lần).

Dữ liệu vào

Dòng đầu chứa bốn số nguyên $n$ , $b$ , $k$ , $x$ cách nhau bởi dấu cách.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — các chữ số trong mỗi khối.

Dữ liệu ra

In ra một số nguyên duy nhất: số cách chọn thoả mãn, lấy modulo $10^{9} + 7$ .

Ràng buộc

$2 \leq n \leq 50 000$
$1 \leq b \leq 10^{9}$
$0 \leq k < x \leq 100$ , $x \geq 2$
$1 \leq a_{i} \leq 9$

Ví dụ

Input	Output	Giải thích
3 2 1 2 3 1 2	6	Các số có thể tạo ra: $11, 13, 21, 23, 31, 33$ . Cả $6$ số đều chia $2$ dư $1$ .
3 2 1 2 6 2 2	0	Các số $22, 26, 62, 66$ đều chẵn nên không chia $2$ dư $1$ .
12 1 5 10 3 5 6 7 8 9 5 1 1 1 1 5	3	Chỉ có $1$ khối, ta cần chọn chữ số chia $10$ dư $5$ — đó là chữ số $5$ . Chữ số $5$ xuất hiện $3$ lần.

Bình luận

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