## Dãy đèn
### Đề
Có $n$ bóng đèn, lúc đầu tắt hết. Trong mỗi lượt, có thể dùng 1 thao tác để biến một đèn:
- Từ tắt $\rightarrow$ xanh
- Từ xanh $\rightarrow$ đỏ
- Từ đỏ $\rightarrow$ tắt

Hỏi dùng đúng $t$ thao tác,có bao nhiêu cách để dãy cuối cùng có $A$ đèn xanh, $B$ đèn đỏ.

### Sol
Về ý tưởng, vẫn dùng QHĐ 3 chiều $\texttt{dp(t,a,b)}$: đã qua $t$ lượt, hiện tại đang có $a$ đèn xanh, $b$ đèn đỏ. Suy ra được sẽ có $c = n-a-b$ đèn tắt.
Để chuyển trạng thái, ta cứ theo 3 trường hợp của đề.
Hàm cộng & nhân viết riêng để đỡ lẫn & dễ nhìn hơn.

### Vấn đề
Mảng trên có kích thước là $600^3$, mỗi số nguyên 32-bit chiếm 4 bytes nên tổng bộ nhớ cần dùng sẽ vào $4 \times 600^3 = 864000000 \,\text{bytes} \approx 823.974609 \,\text{MB}$
Để ý rằng $\texttt{dp(t)}$ chỉ tính hoàn toàn từ $\texttt{dp(t-1)}$ nên chỉ cần hai mảng 2 chiều là đủ.
Cụ thể, tạo một mảng $\texttt{cur}$ tượng trưng cho $\texttt{dp(t)}$, mảng $\texttt{nxt}$ tượng trưng cho $\texttt{dp(t+1)}$.
Ta tính $nxt$ từ $\texttt{cur}$, sau đó lại gán $\texttt{cur = nxt}$ và $\texttt{nxt = \{0\}}$ để tính những trường hợp sau đó.

### Code full