Đếm xâu
Xem dạng PDFThông tin
Chi tiết
Dạng bài
Ngôn ngữ cho phép
Assembly, AWK, C, C++, C++20, C++23, Go, Java, Kotlin, Pascal, Perl, PyPy, Python, Rust, Scratch, SED, Text
Điểm:
100,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Cho xâu nhị phân ~s~ độ dài ~n~. Bạn được thực hiện các thao tác sau bao nhiêu lần tùy ý:
- Xóa ~x~ số
0kề nhau. - Xóa ~y~ số
1kề nhau. - Đổi vị trí ~2~ số
0và1liền kề.
Đếm xem sau một số hữu hạn các thao tác (có thể không thực hiện bất cứ thao tác nào), có bao nhiêu xâu nhị phân độ dài ~m~ khác nhau có thể được tạo ra. Hai xâu nhị phân khác nhau khi chúng có một vị trí mà ở xâu này là 0 nhưng xâu còn lại là 1.
Input
- Dòng đầu tiên chứa bốn số nguyên ~n, m, x, y~ (~1 \le m \le n \le 2 \times 10^5; 0 \le x, y \le n~).
- Dòng thứ hai chứa xâu nhị phân ~s~.
Output
In ra một số nguyên duy nhất là kết quả của bài toán chia lấy dư cho ~10^9 + 7~.
Scoring
- Subtask 1 (25% số điểm): ~n = m~.
- Subtask 2 (25% số điểm): ~n \le 20~.
- Subtask 3 (25% số điểm): ~n \le 2000~.
- Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.
Ví dụ
Input
5 3 1 2
00011
Output
4
Bình luận
Ta giả sử xâu sau khi biến đổi còn lại ~a~ số ~0~ và ~b~ số ~1~
Gọi số lượng số ~0~ và ~1~ ban đầu lần lượt là ~Z~ và ~O~
Mỗi lần ta phải xóa đi ~x~ số ~0~ nên ~a=Z-kx \, (k \in N)~, hay nói cách khác là ~(Z-a)\, \vdots\, x~
Tương tự với số ~1~, ta cũng có: ~(O-b)\, \vdots\, y~
Ta nhận thấy ~0~ và ~1~ có thể đổi vị trí tùy ý cho nhau nên ta chuyển đổi bài toán thành: Có bao nhiêu cách xếp ~a~ số ~0~ vào ~m~ vị trí cho trước. Dễ thấy sẽ có ~\binom{m}{a}~ cách
Từ đó chỉ cần duyệt tìm ~a, b~ phù hợp và cộng dồn ~\binom{m}{a}~ để lấy đáp án.