Luogu6750 [NOI Online #3 提高组] 优秀子序列

题意：给出自然数序列 ，对于 的子序列 ，若 中任意两个元素按位与为 ，则称 为优秀子序列。

定义 的权值为 ，求所有优秀子序列的权值和。

答案对 取模，，，时限 。

---

记值域为 。 的性质差，考虑直接对 分别求出 的方案数。根据题目中的规则，不难联想到集合的不交并。可以发现答案是集合幂级数 的各项系数。

对其先取 后 。 只有 时为 ，其他情况为 ，故 求 即可。从 的组合意义（生成集合）也可以得到相同的结论。复杂度 （即 ）。