Preparing NOJ

带劲的and和

1000ms 65536K

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_{i=1}^{n-1} \sum_{j=i+1}^{n} f(i,j) \times \max(v_i, v_j) \times (v_i \& v_j)$$$

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

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

Input:

第一行一个数,表示数据组数$$$T$$$。

每组数据第一行两个整数$$$n,m$$$;第二行$$$n$$$个数表示$$$v_i$$$;接下来$$$m$$$行,每行两个数$$$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
5 5
3 9 4 8 9 
2 1
1 3
2 1
1 2
5 2

Sample Output:

99

Info

HDU

Provider HDU

Origin 2018“百度之星”程序设计大赛 - 复赛

Code HDU6411

Tags

Submitted 78

Passed 19

AC Rate 24.36%

Date 06/03/2019 16:58:27

Related

Nothing Yet