带劲的and和
题意
度度熊有一张n个点m条边的无向图,第i个点的点权为vi。
如果图上存在一条路径使得点i可以走到点j,则称i,j是带劲的,记f(i,j)=1;否则f(i,j)=0。显然有f(i,j)=f(j,i)。
度度熊想知道求出:
$\sum_{i=1}^{n−1}\sum_{j=i+1}^nf(i,j)×max(v_i,v_j)×(v_i&v_j)$
其中&是C++中的and位运算符,如1&3=1, 2&3=2。
请将答案对109+7取模后输出。
思路
先处理连通块。
这里我用的是并查集,也可以用tarjan,然后对于每个连通块里的元素,我们按照从小到大排序。
由于比如 9 8 7 这部分时,默认我们已经知道9是最大的元素,那么一定是9*(9&8+9&7),由于与运算是只有两位上的数字均为1时才能有贡献,那么也就是说,我们不需要对于每两个数字都计算&运算,而可以对每一个数字的二进制位进行处理,当第i位上为1时,count[i]++,只有count[i]上的数>=2时,才算对于这个有了贡献,并且我们是用同一的9去进行与运算,在count位>=2时,也只有满足当9上的第i位也为1时才算数。
因此从小到达排序之后,从第一个元素开始,在它前面的元素一定比它小,因此我们只要对于这个元素上为1的位进行查询,看它的count是否大于等于2,然后确定是否产生贡献,ans+了后再把当前元素的这一位的count[i]++即可。
看!代码
1 |
|