CF449D

· · 题解

设 f(s) 为最终 and 的的结果包含 s 中所有的 1 的方案数。

若 popcount(x) 是偶数，那么答案加上这个 f(x)，否则减去 f(x)。

考虑求出所有满足 $x$ and $s = x$ 的 $x$，然后这些数可以任意选择，只是至少需要选择一个。 但是这些 $x$ 的数量如何求呢？ 可以将这个过程视为一个 20 维的后缀和，每一维大小为 $2$，使用 sosdp 搞定。