Giống bò cân bằng (Khó)

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

Hướng tiếp cận

Cùng thuật toán DP $O(N^2)$ như bài Silver, với nhận xét tối ưu hóa tương tự.

Nhận xét quan trọng

1. $dp[i][a]$ = số cách gán $i$ ký tự đầu với A có $a$ dấu ( chưa khớp. Số chưa khớp của B xác định qua $(i,a)$.
2. Modulo $2012$.
3. $N\le 1000$: $O(N^2)$ là ${10}^6$ phép tính, đủ nhanh.

Thuật toán

Như bài Silver: DP tiến, cập nhật mảng 1D tại mỗi bước. Kết quả là $dp[0]$.

Độ phức tạp

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