Subtask 1, 2

Ta sử dụng quy hoạch động cho từng truy vấn: ~dp(i, num)~ là tổng của tích của các phần tử trong các tập con có ~num~ phần tử. Công thức: ~dp(i, num) = dp(i-1,num) + dp(i-1,num-1) \times a_i~.

Độ phức tạp thuật toán: ~O(n \times k)~.

Thuật toán chuẩn

Ta sử dụng kĩ thuật giải quyết truy vấn tĩnh bằng chia để trị cùng với quy hoạch động để giải quyết bài toán này.

Xét đoạn ~[L,R]~, ta trả lời các truy vấn ~l~ ~r~ ~k~ mà ~L \le l \le mid=\frac{l+r}{2} < r \le R~.

Gọi ~dpL(i, num)~ là tổng của tích của các phần tử trong các tập con có ~num~ phần tử của đoạn ~[i, mid]~, tương tự với ~dpR(j, num)~ của đoạn ~[mid+1,j]~.

Kết quả cho truy vấn này là ~\prod dpL(l, k') \times dpR(r, k - k')~.

Độ phức tạp thuật toán: ~O(n\space log\space n \times k+q(log\space n+k))~.