題目描述

傳送門

題解

剛開始想的有問題，因為很多子集和可能為同一個數 f(i)表示和為i的子集一共有多少個，那么每加進一個數x，f(i+x)+=f(i) 這樣的話時間是O((∑ai)2)$O((/sum a_i)^2)$的，考慮怎么優化 很顯然最終的答案只與f的奇偶有關，那么讓f(i)表示和為i的子集的個數%2的值 轉移就變成了f(i+x)^=f(i) 可以把整個f看成一個二進制數，這樣就是左移一下然后做異或 直接搞成二進制數太大了，用bitset搞一下就行了

代碼