百度之星 2018 复赛 1003. 带劲的 and 和

发表于 更新于 本文字数： 2.6k 阅读时长 ≈ 5 分钟

Accepts: 791 Submissions: 2435
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)

Problem

Description

度度熊专门研究过 “动态传递闭包问题”，他有一万种让大家爆蛋的方法；但此刻，他只想出一道简简单单的题 —— 至繁，归于至简。

度度熊有一张 n 个点 m 条边的无向图，第 $i$ 个点的点权为 $v_i$。

如果图上存在一条路径使得点 i 可以走到点 j，则称 i,j 是带劲的，记 $f (i,j)=1$；否则 $f (i,j)=0$。显然有 $f (i,j) = f (j,i)$。

度度熊想知道求出：$\sum ^{n-1}{i=1} \sum^{n}{j=i+1} f(i, j) \times \max(v_i, v_j) \times (v_i & v_j)$

这里是只喵QAQ

其中 $&$ 是 C++ 中的 and 位运算符，如 $1 & {3}=1, 2 & 3=2$。

请将答案对 $10^9+7$ 取模后输出。

Input

第一行一个数，表示数据组数 TT。

每组数据第一行两个整数 n,m；第二行 n 个数表示 $v_i​$；接下来 mm 行，每行两个数 u,v，表示点 u 和点 v 之间有一条无向边。可能有重边或自环。

数据组数 T=50，满足：

  • $1 \le n,m \le 100000$
  • $1 \le v_i \le 10^9$

其中 90% 的数据满足 $n,m \le 1000$

Output

每组数据输出一行，每行仅包含一个数，表示带劲的 and 和。

Sample Input

1
2
3
4
5
6
7
8
1
5 5
3 9 4 8 9 
2 1
1 3
2 1
1 2
5 2

Sample Output

1
99

Solution

先放下官方题解吧

比较简单的数据结构题，需要掌握位运算每一位是独立的性质，难度 3 分。

因为是无向图，所以有 f (i,j) = f (j,i) f (i,j)=f (j,i)，不妨用并查集得到图上各个连通块，连通块中每对点的 ff 均为 1，而不同连通块的点对互不影响。

求和的式子中有 $\max$ 一项，不妨对于每个联通块中的点，将它们的权值 vv 从小到大排序，这样枚举到一个点，计算它和前面点之间的贡献时，$\max$ 就是当前点的权值。

还需要处理 && 运算符，这是一个经典的套路，只需要对于二进制的每一位统计出有多少个点在这一位上是 1，对于每一位分开计算贡献即可。举个例子，如果要计算权值 11 和权值 7 的贡献，则有

$max(7,11) \times (7 & 11) = 11 \times ((1 + 2 + 4) & (1 + 2 + 8)) = 11 \times 1 + 11 \times 2$

复杂度为 $O (n \log n + n \times 30)$，因为二进制位有 30 个。

并查集和排序自己想到了，但按位的操作自己没有见过，这次也算是见识到了。

用一个 dp 数组记录下比它小的数字该位有多少个 1 就吼惹。

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+7;
#define LL long long int
const LL mod=1e9+7;
vector<int>ufs[MAXN];
int fa[MAXN];
LL w[MAXN];
int n;
int u_find(int p)
{
    while(p!=fa[p])
    {
        fa[p]=fa[fa[p]];
        p=fa[p];
    }
    return p;
}

void ufsunion(int x, int y)
{
    x=u_find(x);
    y=u_find(y);
    if(x==y)
        return;
    else
    {
        fa[y]=x;	//提交的代码没用ufs路径优化
    }
}
int main()
{
    int T,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<=n; i++)
            ufs[i].clear();
        for(int i=0; i<n; i++)
            scanf("%I64d",&w[i]);
        for(int i=0; i<=n; i++)
            fa[i]=i;
        int u,v;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&u,&v);
            u--,v--;
            ufsunion(u,v);
        }
        LL ans=0;
        for(int i=0; i<n; i++)
            ufs[u_find(i)].push_back(w[i]);
        for(int i=0; i<n; i++)
        {
            if(ufs[i].empty())
                continue;
            sort(ufs[i].begin(),ufs[i].end());
        }
        int dp[32];
        for(int i=0; i<n; i++)
        {
            memset(dp,0,sizeof(dp));
            int len=ufs[i].size();
            for(int j=0; j<len; j++)
            {
                LL it=ufs[i][j];
                for(int j=0; j<30; j++)
                {
                    if(it&(1<<j))
                    {
                        ans=(ans+(1LL*it*dp[j]%mod)*(1<<j))%mod;	//计算当前数字每一位的贡献
                        dp[j]++;		//更新该位1的个数
                    }
                }
            }
        }
        printf("%I64d\n",ans);
    }
}