Author: Copium

Ý tưởng:

Xét mảng ~a[1…n]~ được xếp theo thứ tự không giảm ~(a_1 \le a_2 \le … \le a_n)~, dễ thấy có ~2^{i-1}~ subsequence nhận ~a_i~ làm phần tử lớn nhất.

Vậy bài toán tương đương dựng mảng ~a[1…n]~ sao cho :

• ~a_i \le a_{i+1}~

• 

Vì mọi số ~a_i~ có dạng ~2^k~ đều thỏa mãn yêu cầu của đề bài, ý tưởng ở đây là ta sẽ sử dụng chúng để khôi phục lại biểu diễn nhị phân của số ~x~.

Xét biểu diễn nhị phân của số ~x~, gọi một bit là bật nếu như bit đó bằng ~1~, ta dựng mảng ~a[1…n]~ sao cho ~n~ chính bằng số bit bật trong biểu diễn nhị phân của ~x~ và mỗi phần tử ~a_i~ sẽ tương đương với một bit bật.

Gọi ~b_i~ là vị trí của bit thứ ~i~ được bật từ bên phải sang, khi biết biểu diễn của số ~x~ trong hệ nhị phân ta có thể tính giá trị của ~x~ trong hệ thập phân bằng công thức sau :

Vậy ta sẽ dựng mảng ~a[1…n]~ sao cho:

• ~2^{i-1} \times a_i = 2^{b_i} ↔ a_i = \frac{2^{b_i}}{2^{i-1}}=2^{b_i - (i-1)}~

Dễ thấy ~b_i \ge (i-1)~ và ~b_{i+1}-b_i \ge 1⟶ a_i \ge a_{i+1}~ nên mảng ~a[1…n]~ luôn thỏa mãn đề bài