给定 \(n\) 个数 \(a_i\)，并生成图 \(G\)
对于 \((i,j)\)，若 \(a_i~ \textrm{and}~ a_j=0\)，那么连接 \(i\to j\)
现在每个点都要被加入集合 \(S\)，有两种方式加入集合：
最大化贡献。
\(n\le 2\times 10^5,a_i\in [0,2\times 10^5]\)
神仙题...我完全没想到点子上。
考虑建一张图，对于 \((i,j)\) 若 \(a_i ~\mathbf{and}~a_j=0\) 就连边 \(i\to j\)
同时我们加入一个点权值为 \(0\)
然后我们让每条边的权值为 \(a_i+a_j\)
不难发现答案是边权和减去点权和。
于是从大到小枚举 \(a_i+a_j=w\)，然后枚举 \(w\) 的子集 \(x\)，连接 \(x\) 和 \(w\oplus w\) 即可。
复杂度 \(\mathcal O(3^{18}\times \alpha)\)
可以考虑 B 开头的生成树算法，每次在一个连通块选一个最大出边连出去，然后可以证明合并次数不超过 \(\log\) 次。
于是对每个元素保留最大出边即可，这个等价于满足为其取反子集的最大值，可以用 dp 算。
每轮都做一次这个 dp 即可，复杂度 \(\mathcal O(2^{18}\log(w) \alpha(w))\)
原文：https://www.cnblogs.com/Soulist/p/13656469.html