C bài 17.E4: Chuỗi ACGT (3)


LÀM BÀI

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 20M

Author:
Problem type

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,GT.
  • 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

  • 3N100

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

43=64 chuỗi có độ dài 3 không chứa ký tự nào ngoài A,C,GT. Trong số đó, chỉ có AGC,ACGGAC vi phạm điều kiện, do đó kết quả là 643=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.

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

There are no comments at the moment.

Zalo