自动搬运

查看原文

来自洛谷，原作者为

	__stdcall **

搬运于2025-08-24 22:05:24，当前版本为作者最后更新于2018-09-06 11:13:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

Prelude

非常良心的送分小水题~

这个题作为T1来讲可能难度偏大，所以定位大概是D2T1。

idea：__stdcall

造数据：__stdcall

---

20 pts

$n \le 10$

随便放的分数，防止有人写挂。

---

40 pts

$n \le 100$

随便放的分数，防止有人写挂。

---

60 pts

$n \le 1000$

暴力分。

枚举两个点，判断她们之间是否有连边，直接模拟即可。

---

80 pts

$n \le 10^6$

我们记popcnt(x)表示x在二进制表示下1的个数。

观察之后不难发现，popcnt(a xor b)的奇偶性和popcnt(a)与popcnt(b)的奇偶性有关系。

具体来说，当popcnt(a)和popcnt(b)是一奇一偶的时候，popcnt(a xor b)是奇数，否则就是偶数。

因此，我们只需要统计每个点的权值的popcnt，用奇数的个数乘以偶数的个数就是答案。

需要注意的是，直接统计popcnt的复杂度是$O(\log v)$的，所以这个算法的时间复杂度是$O(n \log v)$。

---

90 pts

$n \le 10^7, v \le 10^6$

不难发现其实是两个生成函数卷在一起，所以直接用FWT就可以了，复杂度$O(v \log v)$。

---

90 pts

$n \le 10^7, v \le 10^6$

用$O(n \log v)$的算法好像不太能过掉$n = 10^7$的数据啊？

但是我们发现会有很多重复的数字，所以先统计一下每个数字的出现次数再做就行了，复杂度$O(v \log v)$。

---

100 pts

$n \le 10^7, v \le 10^9$

如果能用$O(1)$的时间统计popcnt就好了，这样的总复杂度就是$O(n)$了。

实际上是可以的，用类似【WC 2017 挑战】的方法，把数字拆分成高16位和低16位，分开统计。预处理之后就可以做到$O(1)$求popcnt了。