「GDKOI2023 提高组」异或图

可以说是计数大杂烩了吧。

我们试着进行容斥：每次选定若干条边，钦定这些边两端的值相等。容斥系数显然是 \((-1)^{|E|}\)。然后对这些连通块我们把它们的最小值当作 \(a_i\) 拿来跑异或的问题。实际上我们就是要把原图划分成若干连通块，答案就是每个连通块的容斥系数之积乘上新异或问题的方案数，对于每种划分方案求和。一个连通块 \(S\) 的容斥系数即是 \(\sum\limits_{E}(-1)^{|E|}\)，其中 \(E\) 是使得 \(S\) 连通的导出子图的子边集。

考虑怎么算容斥系数：继续容斥。我们考虑集合 \(S\) 被分割成了若干个互相的独立的子集，其中被钦定的某个节点（例如 \(\text{lowbit(S)}\)）被分到了连通块 \(T\) 内，那么减去的贡献 \(T\) 的容斥系数乘以 \(S\backslash T\) 内部边集随便选的值。这一部分就能够 \(\mathcal O(3^n)\) 计算。

那么接下来要算出每个集合的异或问题方案数。我们考虑称某一个数位 \(d\)，如果对于所有 \(i\) 都有 \(b_i(d)=a_i(d)\)，那么这个数位是紧贴的。考虑枚举从高到低第一个不紧贴的数位（要判断更高位异或值是否满足要求），然后钦定这个数位上有至少一个限制值为 \(1\) 但是选了 \(0\)。然后我们考虑其他数位所对应的数，不管更低位怎么选，它都可以来调控使得最后异或为 \(C\)。所以方案数是易于计算的。故可以对于某一位，对每个数顺次 dp。这一部分总复杂度是 \(\mathcal O(2^n n\log V)\) 的。

然后再划分集合，并记录一下最小值集合就完了，这一部分状压 dp 时空复杂度 \(\mathcal O(4^n)\)。

但是显然过不去，考虑优化最后这个 dp。我们按 \(a\) 值从小到大排，那么每一次没有被选的最小数将作为新集合的最小值。发现我们主要的矛盾是同时记录哪些被选，哪些是最小值。我们优化一下状态，记录最小的没被选的数的位置，比他小的数，我们记录它们是否是最小值，比它大的数，记录它是否被选。这样这个 dp 的复杂度就被优化到 \(\mathcal O(3^n n)\) 了。至此，本题就通过了。

感觉最精妙的就是最后这一步优化状态定义了啊。