Dãy con
Đề bài
Mô tả
Cho một xâu độ dài và một số nguyên dương . Hãy đếm số xâu phân biệt có thể thu được bằng cách xóa đúng ký tự khỏi xâu . Vì đáp án có thể rất lớn, hãy in ra đáp án theo modulo .
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và : độ dài xâu và số ký tự cần xóa (, ).
- Dòng thứ hai chứa xâu độ dài . Mọi ký tự của xâu đều là chữ cái tiếng Anh in thường.
Dữ liệu ra
In ra đáp án, theo modulo .
Ràng buộc
- chỉ gồm chữ cái tiếng Anh in thường.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 9 2 aaabbbccc |
6 | Các xâu thu được là aaabbbc, aaabbcc, aaabccc, aabbbcc, aabbccc, abbbccc. |
| 6 2 abcabc |
15 | Cả cách xóa hai ký tự đều cho các xâu khác nhau. |
Bình luận