题解

思路

由于 $0\le a_i<64$，任意子序列的按位与结果也只可能是 $0$ 到 $63$。可以按“当前按位与结果”统计子序列数量。

做法

小规模枚举所有非空子集，直接计算按位与。

若数组全相等为 $x$，任何非空子序列的按位与都为 $x$；当 popcount(x)=k 时答案为 $2^n-1$，否则为零。

一般情况维护 dp[mask]，表示处理过的元素中按位与恰为 mask 的非空子序列数。读入新元素 $x$ 时：原子序列可以不选 $x$；单独选 $x$ 新增一个状态；每个旧状态 mask 选入 $x$ 后转移到 mask & x。全部过程对模数取模。

正确性证明

处理新元素时，每个非空子序列唯一地分为三类：不包含新元素、只包含新元素、包含新元素且此前已有元素。三类分别对应保留原状态、加入单元素状态、从 mask 转移到 mask & x，且互不重叠、覆盖全部子序列。归纳可知最终 dp[mask] 精确统计按位与为该掩码的非空子序列。求和所有 popcount 为 $k$ 的状态即为答案。

复杂度分析

每个元素遍历 64 个状态，时间复杂度 $O(64\sum n)$，空间复杂度 $O(64)$。