推 DJYOSHITAKA: 別捲了 05/20 11:54
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.46.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716176447.A.16C.html
1863. Sum of All Subset XOR
稍微理解一下O(n)的解法
我們將subset sum拆解為每位的結果相加
先從bit 0看 可以將subset拆成包含a_n與不包含的兩種
因此如果a_n bit 0為1 則整個subset bit 0的1的數量為Len / 2 for any n
我們OR 所有數就可以知道該位是否要算
ans = or sum * n / 2
不過要一開始就想到還真難
--