Subtask 1: ~n \le 8~

Ta có thể sử dụng quy hoạch động với bitmask để giải quyết subtask này. Ta có thể mã hóa trạng thái của các bóng đèn vào một dãy nhị phân ~mask~ độ dài ~n~, bit thứ ~i~ của ~mask~ là ~1~ khi bóng đèn thứ ~i~ bật, và ngược lại bit thứ ~i~ sẽ là ~0~. Gọi ~s_{mask}~ là trạng thái đã được mã hóa của các bóng đèn ban đầu.

Định nghĩa ~\mathrm{dp}_{i, mask}~ là ~\mathrm{true}~ nếu tồn tại dãy thao tác ~i~ thao tác đầu tiên (trong ~n~ thao tác đang xét) có thể để được trạng thái các bóng đèn bật định nghĩa bởi ~mask~, ngược lại ~\mathrm{dp}_{i, mask} = \mathrm{false}~. Sẽ tồn tại dãy thao tác thỏa mãn đề bài nếu như tồn tại một ~mask~ mà ~\mathrm{dp}_{n, mask} = \mathrm{true}~.

Ta có trường hợp cơ bản:

$$\mathrm{dp}_{0, mask} = \left\lbrace \begin{array}{lr} \mathrm{true} & \quad(mask = s_{mask})\\ \mathrm{false} & \quad(mask \ne s_{mask}) \end{array} \right.$$

Để tính toán ~\mathrm{dp}~, ta định nghĩa ~f_i~ là dãy các thao tác có thể được thực hiện, mỗi thao tác là tập các bóng đèn có thể thay đổi trạng thái. Tập hợp này cũng có thể được mã hóa sử dụng bitmask. Ví dụ, với ~n = 4~, ta có ~f_1 = \lbrace \texttt{1000}, \texttt{0100}, \texttt{0010}, \texttt{0001} \rbrace~, ~f_2 = \lbrace \texttt{1100}, \texttt{0110}, \texttt{0011}, \texttt{1001} \rbrace~.

Từ đây ta có công thức cho ~\mathrm{dp}~. ~\mathrm{dp}_{i, u} = \mathrm{true}~ khi tồn tại thao tác ~x \in f_i~ mà ~\mathrm{dp}_{i - 1, (u \oplus x)} = \mathrm{true}~ (trong đó ~\oplus~ là phép toán XOR bit). Nếu không tồn tại ~x~, ~\mathrm{dp}_{i, u} = \mathrm{false}~.

Về phần triển khai, ta có thể duyệt qua toàn bộ ~x~ trong ~f_i~ với đoạn code sau:

int rotate_mask(int length, int mask) {
  return (mask >> 1) | ((mask & 1) << (length - 1));
}

// ...

for (int i = 1; i <= n; ++i) {
  int mask = (1 << i) - 1;
  for (int j = 0; j < n; ++j, mask = rotate_mask(n, mask))
  { /* ... */ }
}

Subtask 2: số lượng đèn bật ban đầu đúng bằng ~k~.

Định nghĩa số lượng bóng đèn bật thay đổi ~C = k - cnt_1~, với ~cnt_1~ là số lượng bóng đèn bật ban đầu. Trong subtask này ta có ~C = 0~.

Từ subtask 1, ta thấy các thao tác tương đương với thao tác XOR bit. Từ đây ta có các nhận xét sau:

1. Đến cuối cùng, một bóng đèn sẽ thay đổi trạng thái so với ban đầu nếu như có lẻ thao tác áp dụng lên bóng đèn này.

2. Thứ tự của các thao tác không quan trọng. Nếu như ta đã có vị trí bắt đầu của các thao tác, ta có thể thực hiện thao tác hai trước thao tác một.

Từ quan sát 1, ta có nhận xét về điều kiện cần để đáp án xảy ra cho subtask 2: tổng số lượng các các vị trí có các thao áp dụng vào phải là một số chẵn, tức ~1 + 2 + \ldots + n = \frac{n(n + 1)}{2}~ là một số chẵn. Nếu điều này không xảy ra, đến cuối cùng ta sẽ có lẻ bóng đèn bị thay đổi, và điều này là không thể vì ~C = 0~ là một số chẵn.

Ở trong subtask này, ta có thể thực hiện các thao tác mà đến cuối cùng các đèn có trạng thái y như ban đầu.

Với ~\frac{n(n + 1)}{2}~ là một số chẵn, dãy thao tác sẽ tồn tại khi ~n \equiv 0 \pmod 4~ hoặc ~n \equiv 3 \pmod 4~.

Với trường hợp ~n \equiv 0 \pmod 4~, tồn tại cách để áp dụng 4 thao tác liên tiếp để trạng thái các bóng đèn không thay đổi. Nếu xét thao tác thứ ~i~, ~i + 1~, ~i + 2~, ~i + 3~, ta có thể bắt áp dụng các thao tác này tại các vị trí ~2, 1, 2, 1~. Có thể nhận thấy tất cả các bóng đèn đều có chẵn thao tác áp dụng lên nó. Dưới đây là minh họa cho 4 thao tác ~3, 4, 5~ và ~6~. Mỗi ô vuông thể hiện vị trí bóng đèn được áp dụng vào tại mỗi thao tác ~i~ từ ~3~ đến ~6~.

$$\begin{array}{r |ccccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline i = 3 & & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & & \\ i = 4 & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & & & \\ i = 5 & & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} \\ i = 6 & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \rule{5mm}{5mm} & \\ \end{array}$$

Với trường hợp ~n \equiv 3 \pmod 4~, ta có thể gộp 3 thao tác đầu tiên ~1~, ~2~ và ~3~ với các vị trí bắt đầu ~2~, ~1~, ~2~, và đưa trường hợp này về trường hợp ~n \equiv 0 \pmod 4~.

Subtask 3: không có điều kiện gì thêm (~n \le 2\cdot 10^5~).

Trong trường hợp này, ta có số lượng bóng đèn bật thay đổi ~C~ bất kì, tuy nhiên điều kiện cần ta có sẽ tương tự: ~\frac{n(n + 1)}{2} \equiv C \pmod 2~. Đây cũng là điều kiện đủ, và cách xây dựng đáp án sau sẽ chứng minh điều đó.

Đầu tiên ta sẽ áp dụng thao tác thứ ~n~ để đổi trạng thái của toàn bộ các bóng đèn. Sau đó ta sẽ thực hiện từ thao tác ~n - 1~ vè thao tác ~1~, và sau tất cả các thao tác, ta muốn ~k~ bóng đèn đầu tiên sẽ bật, và ~n - k~ bóng đèn cuối sẽ tắt.

Tại thoa tác thứ ~i~ (lưu ý ta đang xét các thao tác theo thứ tự từ ~n - 1~ về ~1~), ta muốn rằng bóng đèn thứ ~n - i~ cần có đúng trạng thái ta muốn (bật khi ~n - i \le k~, và tắt trong trường hợp ngược lại).

Nếu như ở thời điểm hiện tại, bóng đèn ~i~ chưa đúng trạng thái, ta sẽ áp dụng thao tác bắt đầu từ vị trí ~n - i~ để bóng đèn này sẽ có trạng thái thay đổi, và ngược lại ta sẽ áp dụng thao tác bắt đầu tại vị trí ~n - i + 1~.

Mã giả của thuật toán như sau, trong đó hàm flip là hàm thay đổi trạng thái của cnt bóng đèn liên tiếp bắt đầu từ from.

void flip(int from, int cnt) { /* ... */ }

void solve() {
  flip(1, n);
  for (int i = n - 1; i >= 1; --i) {
    int u = n - i;
    int target_state = u <= k;
    if (bulb[i] != target_state) flip(u, i);
    else flip(u + 1, i);
  }
}

Có thể thấy rằng thao tác này sẽ không ảnh hưởng đến các bóng đèn đã có trạng thái cố định trước đó. Bởi vì vị trí bắt đầu của các thao tác không bao gồm các bóng đền trước, và thao tác cũng sẽ không áp dụng đến bóng đèn ~1~.

Cách xây dựng đáp án là cách xây dựng đúng. Thật vậy, cách xây dựng đáp án sẽ đảm bảo rằng ta có đáp án cho ~n - 1~ bóng đèn ban đầu đúng. Điều kiện cần của chúng ta cũng nói rằng tính chẵn lẻ của số thao tác và số bóng đèn cần đổi cũng cần giống nhau, như vậy tính chắn lẻ (sự bât/tắt) của bóng đèn cuối cùng cũng sẽ được đảm bảo sau khi thuật toán trên hoàn thành.

Về triển khai, để có thể thay đổi trạng thái bóng đèn một cách nhanh chóng, ta có thể sử dụng tổng tiền tố, và tính toán giá trị của tổng ngay trong vòng lặp.