題目描述

傳送門

題解

剛開始想的有問題，因?yàn)楹芏嘧蛹涂赡転橥粋€數(shù) f(i)表示和為i的子集一共有多少個，那么每加進(jìn)一個數(shù)x，f(i+x)+=f(i) 這樣的話時間是O((∑ai)2)$O((/sum a_i)^2)$的，考慮怎么優(yōu)化 很顯然最終的答案只與f的奇偶有關(guān)，那么讓f(i)表示和為i的子集的個數(shù)%2的值 轉(zhuǎn)移就變成了f(i+x)^=f(i) 可以把整個f看成一個二進(jìn)制數(shù)，這樣就是左移一下然后做異或 直接搞成二進(jìn)制數(shù)太大了，用bitset搞一下就行了

代碼