305482: CF1039C. Network Safety
Memory Limit：512 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Network Safety
题意翻译
题意： 给你一个有$n$点个和$m$条边的图，第$i$个点的权值为$c_i$。 定义图为安全的条件对于所有的边都保证$c_l≠c_r$ 请你求出对于任意的$x$，集合$s$中所有点的点权$xor\quad x$后图仍然安全，这样的$x$和$s$的组合的数量。 答案对于$1e9+7$取模 保证一开始给出的图是安全的。 输入格式： 第一行一共三个整数$n(n<=500000),m(m<=min(\frac{n*(n-1)}{2},500000)),k(k<=60)$ 第二行一共$n$个整数$c_i(c_i<=2^k-1)$ 接下来的$m$行每行两个整数$l,r$，表示$l$和$r$之间有边 输出格式： 一共一个整数，表示答案题目描述
The Metropolis computer network consists of $ n $ servers, each has an encryption key in the range from $ 0 $ to $ 2^k - 1 $ assigned to it. Let $ c_i $ be the encryption key assigned to the $ i $ -th server. Additionally, $ m $ pairs of servers are directly connected via a data communication channel. Because of the encryption algorithms specifics, a data communication channel can only be considered safe if the two servers it connects have distinct encryption keys. The initial assignment of encryption keys is guaranteed to keep all data communication channels safe. You have been informed that a new virus is actively spreading across the internet, and it is capable to change the encryption key of any server it infects. More specifically, the virus body contains some unknown number $ x $ in the same aforementioned range, and when server $ i $ is infected, its encryption key changes from $ c_i $ to $ c_i \oplus x $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Sadly, you know neither the number $ x $ nor which servers of Metropolis are going to be infected by the dangerous virus, so you have decided to count the number of such situations in which all data communication channels remain safe. Formally speaking, you need to find the number of pairs $ (A, x) $ , where $ A $ is some (possibly empty) subset of the set of servers and $ x $ is some number in the range from $ 0 $ to $ 2^k - 1 $ , such that when all servers from the chosen subset $ A $ and none of the others are infected by a virus containing the number $ x $ , all data communication channels remain safe. Since this number can be quite big, you are asked to find its remainder modulo $ 10^9 + 7 $ .输入输出格式
输入格式
The first line of input contains three integers $ n $ , $ m $ and $ k $ ( $ 1 \leq n \leq 500\,000 $ , $ 0 \leq m \leq \min(\frac{n(n - 1)}{2}, 500\,000) $ , $ 0 \leq k \leq 60 $ ) — the number of servers, the number of pairs of servers directly connected by a data communication channel, and the parameter $ k $ , which defines the range of possible values for encryption keys. The next line contains $ n $ integers $ c_i $ ( $ 0 \leq c_i \leq 2^k - 1 $ ), the $ i $ -th of which is the encryption key used by the $ i $ -th server. The next $ m $ lines contain two integers $ u_i $ and $ v_i $ each ( $ 1 \leq u_i, v_i \leq n $ , $ u_i \ne v_i $ ) denoting that those servers are connected by a data communication channel. It is guaranteed that each pair of servers appears in this list at most once.
输出格式
The only output line should contain a single integer — the number of safe infections of some subset of servers by a virus with some parameter, modulo $ 10^9 + 7 $ .
输入输出样例
输入样例 #1
4 4 2
0 1 0 1
1 2
2 3
3 4
4 1
输出样例 #1
50
输入样例 #2
4 5 3
7 1 7 2
1 2
2 3
3 4
4 1
2 4
输出样例 #2
96