Vì giới hạn $n$ nhỏ, ta có thể backtrack tất cả trò chơi khác nhau, tổng cộng $2^n$ trò chơi. Với mỗi trò chơi, ta kiểm tra bằng cách xét từng cách imposustor giết một, nếu có ít nhất một cách thỏa mãn thì đó là trò chơi gay cấn, trong mỗi trò chơi có $2^i$ cách imposustor chọn người (với $i$ là số imposustor). Độ phức tạp để duyệt mỗi trò chơi là $O(2^i\times n)$

Vì số testcase là quá lớn, thay vì ta backtrack từng test thì ta lưu trước kết quả của từng giá trị $n$ từ $1$ đến $12$ rồi xuất ra kết quả trong $O(1)$

Giới hạn $n$ vẫn nhỏ, ta thử suy nghĩ đến cách kiểm tra trò chơi nhanh hơn:

Ta có thể tham lam để kiểm tra như sau: Ta sẽ ưu tiên về việc imposustor giết người ở bên trái, trong trường hợp không thể giết người ở bên trái ta mới duyệt bên phải, như vậy độ phức tạp chỉ còn $O(n)$

Ta cũng làm tương tự như subtask 1 là lưu trước kết quả của từng giá trị $n$ từ $1$ đến $20$ rồi xuất ra kết quả trong $O(1)$

Theo ý tưởng duyệt tham lam mà ta đã nói ở subtask 2, ta có thể coi như 1 imposustor là 1 nhóm gồm imposustor vị trí $i$ và 1 crewmate vị trí $i-1$ hoặc $i+1$. Ví dụ: Trong trò chơi 0110, ta có thể chia $1$ và $2$ vào 1 nhóm; $3$ và $4$ vào 1 nhóm.

Bài toán từ đây đã được đơn giản hóa, chuyển sang quy hoạch động.

Ta gọi $dp[i][j]\ (1\le i\le n, 0\le j<3)$ là số cách chia nhóm tới vị trí thứ $i$, và trạng thái ở ô cuối cùng là $j$. Trong đó:

• $j=0$: Ô cuối cùng là crewmate an toàn
• $j=1$: 2 ô cuối cùng tương ứng với imposustor ở vị trí $i$, còn crewmate ở vị trí $i-1$, imposustor vị trí $i$ sẽ giết crewmate vị trí $i-1$
• $j=2$: 2 ô cuối cùng tương ứng với imposustor ở vị trí $i-1$, còn crewmate ở vị trí $i$, imposustor vị trí $i-1$ sẽ giết crewmate vị trí $i$

Sau khi tiền xử lý trước mảng $dp$, ta có thể xuất kết quả ra trong $O(1)$

Độ phức tạp: $O(n)$

Giả sử ta lưu tất cả giá trị $dp$ thì chắc chắn sẽ $MLE$ trong subtask này.

Ý tưởng chính trong subtask này là ta sắp xếp lại truy vấn, ưu tiên xuất ra kết quả với $n$ nhỏ, xong mới tới $n$ lớn. Ở đây ta không cần lưu hết các kết quả từ $1$ đến $5\times 10^7$ nên ta có thể tối ưu để giảm bộ nhớ

Độ phức tạp: $O(n)$

Dựa vào công thức $dp$, ta có thể suy ra được công thức truy hồi theo ma trận như sau:

Ta đặt $p_k=\begin{pmatrix} dp_{k-1,0} & dp_{k-1,1} & dp_{k-1,2} & dp_{k,0} & dp_{k,1} & dp_{k,2} \end{pmatrix}$ và $M=\begin{pmatrix} 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 \end{pmatrix}$

Tới đây ta suy ra được $p_k=p_{k-1}\times M=p_2\times M^{k-2}$

Trong đó $p_2=\begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}$

Tới đây, ta có thể sử dụng nhân ma trận để tính $M^{k-2}$ xong nhân với $p_2$ và giải quyết trong $O(6^3\times log(n))$ mỗi testcase, nhưng điều này là không đủ để giúp bạn AC bài này. Ta cần một cách tối ưu hơn

Ý tưởng: Ta sẽ tính trước $M^1,M^2,M^4,\dots,M^{2^{59}}$. Ta không cần phải tính $M^{k-2}$ mà có thể chia $k-2=2^{a_1}+2^{a_2}+2^{a_3}+\dots+2^{a_x}\ (a_i>a_{i+1})$ sau đó sẽ nhân $p_2$ với lần lượt từng $M^{2^{a_1}},M^{2^{a_2}},M^{2^{a_3}},\dots,M^{2^{a_x}}$. Ta có thể tách $k-2$ thành dãy $a$ bằng biểu diễn nhị phân. Độ phức tạp cho cách trên sẽ là $O(6^2\times log(n))$, đủ để AC bài này