题解

思路

先把两个阵营的按位与必须相等转化为逐位限制，再用容斥统计所有有序二分方案。小范围直接枚举警察集合；有效位较少时直接枚举每一位的容斥归属；满分范围把容斥项按位集合合并，并用超集和与诱导图连通分量计算。

做法

子任务一

枚举所有非空且非全集的奶牛子集作为警察阵营，分别计算两个阵营的按位与并比较。复杂度为 $O(N2^N)$。

子任务二

先删去在所有数中恒为零或恒为一的位，只保留同时出现过零和一的有效位。此时有效位不超过 $6$。

对于每个有效位，容斥中有三种选择：不选、要求警察阵营的所有奶牛在该位为一、要求小偷阵营的所有奶牛在该位为一。枚举全部三进制状态后，检查每种合作指数能被分配到哪些阵营。若一头奶牛两个阵营都可去，就贡献两种选择；若两个阵营都不能去，则该容斥项为零。复杂度为 $O(N+3^6 2^6)$。

子任务三

设全部奶牛合作指数的按位与为 $G$。若两个阵营的按位与相等，那么把两个阵营合并后按位与仍不变，所以它们的按位与都必须等于 $G$。

删去恒定不变的位后，设剩余有效位数为 $K$。对位集合 $Z$，令 $F(Z)$ 表示合作指数包含 $Z$ 中全部位的奶牛数量。全部 $F(Z)$ 可以通过超集和在 $O(K2^K)$ 时间内求出。

在有效位上建立无向图：若存在一头奶牛在位 $x,y$ 上都为零，就连接 $x,y$。对于一个容斥位集合 $Z$，将它的每一位指定给警察条件或小偷条件。为了使每头奶牛至少能进入一个阵营，同一头奶牛缺少的所有 $Z$ 中位必须指定给同一侧。因此，$Z$ 的诱导子图中每个连通分量只能整体选择一侧，共有 $2^{c(Z)}$ 种指定方式，其中 $c(Z)$ 是连通分量数。

包含 $Z$ 全部位的 $F(Z)$ 头奶牛在两侧都可放置，各贡献两种选择。由容斥原理，答案为

若没有有效位，所有奶牛的合作指数完全相同，答案直接为 $2^N-2$，减去两个空阵营方案。

正确性证明

两个阵营按位与相等时，它们的公共值等于全体奶牛的按位与 $G$，所以只需保证每个有效位在两个阵营中都至少出现一个零。

对某一阵营缺少零的事件进行容斥，相当于要求该阵营所有奶牛在选中的位上均为一。一个有效位不可能同时要求两个阵营，因为该位至少有一头奶牛为零；因此每一位只有不选、指定警察、指定小偷三种状态。

固定容斥位集合 $Z$ 后，一头奶牛若缺少分给两侧的位，就无法进入任何阵营。要求每头奶牛缺少的位同侧，等价于共同缺失的位必须同色，也等价于诱导图每个连通分量同色，所以有 $2^{c(Z)}$ 种位指定。包含全部 $Z$ 位的奶牛不受指定限制，各有两种阵营选择，贡献 $2^{F(Z)}$。乘积并按 $(-1)^{|Z|}$ 求和即得到全部且仅有合法方案。

复杂度分析

设有效位数 $K\le 20$。时间复杂度为 $O(NK+K2^K)$，诱导图连通分量计算也在 $O(K2^K)$ 内；空间复杂度为 $O(N+2^K)$。