C bài 17.E4: Chuỗi ACGT (3)
Bạn được cho một số nguyên N. Tìm số lượng chuỗi có độ dài N thỏa mãn các điều kiện sau, modulo 109+7:
- Chuỗi không chứa ký tự nào ngoài A,C,G và T.
- Chuỗi không chứa AGC là chuỗi con.
- Điều kiện trên không bị vi phạm khi hoán đổi hai ký tự liền kề một lần.
Ghi chú
Một chuỗi con của một chuỗi T là một chuỗi thu được bằng cách loại bỏ không hoặc nhiều ký tự từ đầu và cuối của T.
Ràng buộc
- 3≤N≤100
INPUT FORMAT
- Đầu vào được cung cấp từ Standard Input theo định dạng sau:
Copy
N
OUTPUT FORMAT
- In ra số lượng chuỗi có độ dài N thỏa mãn các điều kiện, modulo 109+7.
Ví dụ:
Input
Copy
3
Output
Copy
61
Có 43=64 chuỗi có độ dài 3 không chứa ký tự nào ngoài A,C,G và T. Trong số đó, chỉ có AGC,ACG và GAC vi phạm điều kiện, do đó kết quả là 64−3=61.
Input
Copy
4
Output
Copy
230
Giải thích ví dụ mẫu
Ví dụ:
Input:
3
Giải thích:
- Có tổng cộng 64 chuỗi độ dài 3 từ các ký tự A, C, G, T. Ba chuỗi "AGC", "ACG", "GAC" vi phạm điều kiện, nên số chuỗi hợp lệ là 64 - 3 = 61.
Ví dụ:
Input:
4
Giải thích:
- Có tổng cộng 256 chuỗi độ dài 4. Số chuỗi vi phạm điều kiện là 26, nên kết quả là 256 - 26 = 230.
- Có tổng cộng 256 chuỗi độ dài 4. Số chuỗi vi phạm điều kiện là 26, nên kết quả là 256 - 26 = 230.
Lời giải bài tập này: Tại đây
Group giải đáp thắc mắc: Lập trình 24h
Fanpage CLB: CLB lập trình Full House- Việt Nam
Youtube: CLB Lập Trình Full House
Comments