Giống bò cân bằng (Dễ)

Lời giải: Giống bò cân bằng (Dễ)

Hướng tiếp cận

Quy hoạch động 2D: $dp[i][a]$ = số cách gán $i$ ký tự đầu với giống A có $a$ dấu ( chưa khớp.

Nhận xét quan trọng

1. Số dấu ( chưa khớp của giống B = tổng dấu ( chưa khớp tính đến vị trí $i$ trừ $a$. Vậy B được xác định bởi $(i,a)$ → giảm từ $O(N^3)$ xuống $O(N^2)$.
2. Gán ký tự thứ $i$ cho giống A hay B đều hợp lệ nếu số ( chưa khớp tương ứng không âm.
3. Modulo $2012$.

Thuật toán

DP tiến từ đầu đến cuối chuỗi, cập nhật $dp[a]$ tại mỗi bước. Kết quả là $dp[0]$ sau khi xử lý toàn bộ chuỗi (khi tổng dấu ( chưa khớp = 0).

Độ phức tạp

• Thời gian: $O(N^2)$
• Bộ nhớ: $O(N)$