题解：P10104 [GDKOI2023 提高组] 异或图

· · 题解

考虑 m=0 怎么做，即没有某些不等的限制。

问题为：给定 n 个数的数列 \lbrace a_i\rbrace，计数 b 的数量使得：

先给出结论，这个子问题的时间复杂度是 O(n\log V)。V=10^{18} 是值域。

有异或和 =C 的很难处理。注意到 C 为某个值与 C=0 并无本质区别，直接转化成异或和为 0。考虑钦定 a_{n+1}=C，计算此时异或和为 0 的方案数 A，再令 a_{n+1}=C-1，方案数为 B，那么显然前 n 个数异或和为 C 的方案数为 A-B。

考虑异或和 =0 怎么做。对于一种特殊情况：a_1>\max_{i=2}^n a_i 时，可以让 a_{2\sim n} 任意取，此时无论如何在更低位都可以找到一个 a_1 满足值的限制，使得异或和 =0，这种情况的方案数为 \prod_{i=2}^n (a_i+1)。

从这个方向进一步考虑，不妨设比第 d 位高的部分的异或和为 0，那么考虑最低 d 位能用以上方式调整的条件，让这个调整的位置是 i，那么要求 b_i 与 a_i 的比 d 位高的部分并不完全重合，那么就要求 b_i\leq a_i-2^{d+1}。

枚举 d=\log V\to 0。只考虑 d 以及 d 位以下的低位。设计 \text{dp} 为：f_{i,0/1,0/1} 表示前 i 个数，是否有位置作为自由元，第 d 位的异或和为 0/1 的贡献积。转移是容易的。

这样可以在 O(n\log V) 的时间解决这个子问题。

考虑原问题怎么做，不难想到容斥。

显然有一个对于边集 S，钦定 S 的边都不满足两端互不相等的做法，这样的复杂度是 O(2^mn\log V)，不能接受。

注意到上述做法的细节：关注 S 中的边构成的连通块，进一步地，大小为奇数的连通块只关注最小的 a_i，大小为偶数的连通块直接乘上 (\min(a_i)+1)。

所以我们可以简化成，连通块被划分成什么样子。

考虑重新分配涉及的边集的容斥系数。(-1)^{|E|} 显然可以拆到每个连通块上求 (-1)^{|E'|} 的积。对于每个连通块，容斥系数即为：导出子图边集中所有使得此点集的连通的边集的，(-1)^{|E'|} 之和。可以 O(3^nn) 预处理这个，记录为 g_S，具体就是钦定一个部分与剩下的部分不连通，进行枚举子集。

直接枚举点集划分是 O(\text{Bell}(n)n\log V) 的，大概能过 n\leq 13。

事实上点集划分会导出，对于所有的 \min(a_i) 且连通块为奇数的序列 c，去跑最开始写的那个东西。不同的点集划分可能导出相同的 c，这样非常浪费，加一个哈希表本质上无法优化复杂度。

考虑枚举这个序列 c，难点在于求它的容斥系数 coef_c。

注意到 \min(a) 可以直接对于所有点按照 a 排序，然后按序从 i=1\to n 进行连通块划分。\text{dp} 当前已经划分的点集的 coef_S。每次枚举到 i 时，1\sim i-1 必然已经划分完毕，对后面造成贡献的只有 i。枚举 i 的连通块 T\subseteq\lbrace i,i+1,i+2,\cdots,n\rbrace，i\in T，直接更新 coef 即可。

时间复杂度 O(3^nn+2^nn\log V)。

提交记录。