Edge solution

__stdcall · 2018-09-06 11:13:37 · 题解

Prelude

非常良心的送分小水题~

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

idea：__stdcall

造数据：__stdcall

20 pts

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

40 pts

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

60 pts

暴力分。

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

80 pts

我们记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

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

90 pts

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

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

100 pts

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

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