Edge solution

### 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了。