Với mỗi $n_i$=$N$, bài toán thực chất là đếm số cách phân tích N thành tổng các số là lũy thừa của 2. Tức là đếm số cách phân tích $N$=$a_1$+$a_2$+⋯+$a_m$ với $a_1$≤$a_2$≤⋯≤$a_m$ mà $a_i$ là lũy thừa của 2, hay $a_i$=$2^k$ ($k\in N$).

• Subtask 1: Vì $N\le 100$ nên số nghiệm của bài toán rất nhỏ do $a_i$ có dạng là lũy thừa của 2. Ta có thể sử dụng thuật toán quay lui kết hợp một vài nhánh cận cơ bản để tìm hết tất cả nghiệm của bài toán.

• Subtask 2: Ở ràng buộc này, đây là một bài toán quy hoạch động cơ bản. Ta gọi $f(N,k)$ là số cách phân tích $N$=$a_1$+$a_2$+⋯+$a_m$ mà $a_1$≤$a_2$≤⋯≤$a_m$≤$2^k$, $a_i$ là các lũy thừa của 2 thì $f(N,k)$=$f(N,k-1)+f(N$-$2^k$,$k$).

  Vì $a_i$=$2^k$≤$N$ nên $0\le k\le lg$N. Do đó, số trạng thái quy hoạch động cũng như độ phức tạp thuật toán sẽ là ${\rm O}(N\times lgN)$.

• Subtask 3: Ràng buộc này buộc chúng ta phải nghĩ ra thuật toán có độ phức tạp ${\rm O}(N)$ có được điểm. Do đó, ta cần có những nhận xét sâu hơn. Ta có thể gọi $f(N)$ là kết quả bài toán.

  Với $N$ lẻ, chắc chắn $a_1$=$1$ nên $f(N)$=$f(N-1)$.

  Với $N$ chẵn, nếu $a_1$=$1$ thì số bộ nghiệm sẽ là $f(N-1)$. Nếu $a_1$≥$2$ thì do các $a_i$ đều là lũy thừa của 2 nên đều chia hết cho 2, do đó ta chia cả 2 vế của phương trình (*) cho 2, số nghiệm giờ đây sẽ là $f(N/2)$. Theo nguyên lý cộng, ta có $f(N)=f(N-1)+f(N/2)$.

  Tóm lại, $f(2n+1)=f(2n)=f(2n-1)+f(n)$ với $f(1)=1$.

•