Mình xin chia sẻ lời giải bài này như sau:

Gọi \(F[n]\) là số cách dán các số lên các con chuồn chuồn sao cho tổng các số sau khi dán chia hết cho \(3\).

Khi đó ta có công thức truy hồi sau: \(F[n]=3 * F[n-1]=3^2*F[n-2]=...=3^{n-1}*F[1]\), với \(F[1]=1\). Do đó \(F[n]=3^{n-1}\)

Đến đây ta sử dụng luỹ thừa nhị phân là bài toán đã được giải quyết.

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

Các bạn có thể tham khảo code tại đây: Link