Cho n số (1<=n<=34) S1 đến Sn ( |Si|<=20m). Đếm số tập con S (gồm cả tập rỗng) có tổng thuộc khoảng A,B ( |A|,|B|<=500m)

Input:
3 -1 2
1
-2
3

Output:
5The following 5 subsets have a sum between -1 and 2:


	0 = 0 (the empty subset)
	1 = 1
	1 + (-2) = -1
	-2 + 3 = 1
	1 + (-2) + 3 = 2


 

Algorithms:

 

Chia đôi tập thành 2 phần => mỗi phần có <=17 phần tử. Tính tổng mỗi tập con của mỗi phần lưu vào 2 mảng.

Sort các tổng trong phần 2.

Xét phần 1, vơi mỗi tổng tạo ra từ nửa này ta chặt nhị phân tìm

i= vị trí của tổng đầu tiền >B-s

j= vị trí tổng đầu tiên >= A-s

res+=i-j

 

Skills:

- upper_bound, lower_bound

upper_bound(y,y+tg+1,B-x[i])

lower_bound(y,y+tg+1,A-x[i])

trả về vị trí con trỏ

Nhớ là tg+1

(WA lần 1,2)

- int BIT(int i,ll x) { return(x&(1<<i));}

Hàm này trả về giá trị của bit i

ví dụ: 9=1001 => BIT(3,9)

- khi làm dạng này, muốn chia đôi tập số thì để tránh phải cộng thêm phần bù thì ta có thể chia thành 2 mảng ngay khi nhập

bitwise