CF1336E2

CF1336E2

考虑答案为：

[F(x)=prod (1+x^{a_i}) ]

设 (G_c(x)=sum [ extrm{popcount}(i)=c]x^i)，那么有对于某个 (c)，答案为 (F(x)G_c(x)[x^0])

对 (F(x)) 取 FWT，观察到 FWT((1+x^{a_i})) 的点值只有 (0/2)，所以整体做完 FWT 之后的点值只有 (2^n) 和 (0)，且任意一位为 (0) 此位的点值就是 (0)

且不为 (0) 的 (i) 会满足 (forall j, extrm{popcount}(i&a_j)mod 2=0)，设 (c(i,j)) 表示 ([ extrm{popcount}(i&j)mod 2=0])，则有如果 (c(i,j)=1,c(k,j)=1)，那么 (c(ioplus j,k)=1)

不难看出 (c(x,y)) 的左右两边都满足此性质，于是两边均为封闭的集合（构成异或意义下的一个群）显然的事实是，(y) 部分的集合就是 (a_i) 处任意异或可以得到的所有可能的值，当此集合变大时，相应的 (x) 处的集合会变小，两个部分均可以使用线性基描述，可以证明两个部分的线性基大小之和为 (m)

此时，我们有两种思路：

• 维护可能异或出来的值并暴力。
• 维护 FWT 后有点值的位置并暴力。

至此，可以在 (mathcal O(2^{m/2})) 的复杂度解决此问题。