傳送門
我們要求的是\([x^0]\prod\limits_{i=1}^n (2x^{a_i}+1)\)，其中乘積定義為集合對稱差卷積。
這個直接做復雜度太高了，考慮優化。注意到在FWT之后，每一個序列中的值要么是\(3\)，要么是\(-1\)，而且這個只跟\(a_i\)有關。如果我們能夠計算出每一個位置的\(3\)和\(-1\)的數量就可以IFWT然后求解。
那么我們不妨對于所有\(x^{a_i}\)加和然后做一遍對稱差卷積。值得注意的事情是和的FWT等于FWT的和，所以最后得到的每一位的結果就是“所有在FWT后當前位置為\(3\)的數組的個數-所有在FWT后當前位置為\(-1\)的數組的個數”。我們有可以知道這兩者的和為\(N\)，就可以快速計算出\(3\)和\(-1\)的數量。
強化版：Global Round 2 H
代碼
)
Hash基礎)
 二)
