自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

搬运于2025-08-24 22:54:42，当前版本为作者最后更新于2024-06-19 15:55:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

• $0\leq b_i\leq a_i$。
• $\bigoplus_{i=1}^nb_i=C$。

先给出结论，这个子问题的时间复杂度是 $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)$。

提交记录。