F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Transform

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1057    Accepted Submission(s): 413


Problem Description
A list of $n$ integers are given. For an integer $x$ you can do the following operations:

+ let the binary representation of $x$ be $\overline{b_{31}b_{30}...b_0}$, you can flip one of the bits.
+ let $y$ be an integer in the list, you can change $x$ to $x \oplus y$, where $\oplus$ means bitwise exclusive or operation.

There are several integer pairs $(S, T)$. For each pair, you need to answer the minimum operations needed to change $S$ to $T$.
 

Input
There are multiple test cases. The first line of input contains an integer $T$ $(T \le 20)$, indicating the number of test cases. For each test case:

The first line contains two integer $n$ and $m$ $(1 \le n \le 15, 1 \le m \le 10^5)$ -- the number of integers given and the number of queries. The next line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^5)$, separated by a space.

In the next $m$ lines, each contains two integers $s_i$ and $t_i$ $(1 \le s_i, t_i \le 10^5)$, denoting a query.
 

Output
For each test cases, output an integer $S=(\displaystyle\sum_{i=1}^{m} i \cdot z_i) \text{ mod } (10^9 + 7)$, where $z_i$ is the answer for $i$-th query.
 

Sample Input
1 3 3 1 2 3 3 4 1 2 3 9
 

Sample Output
10
 

Hint

$3 \to 4$ (2 operations): $3 \to 7 \to 4$

$1 \to 2$ (1 operation): $1 \oplus 3 = 2$

$3 \to 9$ (2 operations): $3 \to 1 \to 9$
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 20:58:20, Gzip enabled