hdu 5637 BestCoder Round #74 (div.2)

Transform

Accepts: 7

Submissions: 49

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

问题描述

给出 $n$ 个整数, 对于一个整数 $x$ , 你可以做如下的操作若干次:

  + 令 $x$ 的二进制表示为 $overline{b_{31}b_{30}...b_0}$ , 你可以翻转其中一个位.
  + 令 $y$ 是给出的其中一个整数, 你可以把 $x$ 变为 $x \oplus y$ , 其中 $\oplus$ 表示位运算里面的异或操作.

现在有若干整数对 $(S, T)$ , 对于每对整数你需要找出从 $S$ 变成 $T$ 的最小操作次数.

输入描述

输入包含多组数据. 第一行有一个整数 $T$   $(T \leq 20)$ , 表示测试数据组数. 对于每组数据:

第一行包含两个整数 $n$ 和 $m$   $10^5)$ , 表示给出整数的数目和询问的数目. 接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, ..., a_n$   $a_i le 10^5)$ .

接下来 $m$ 行, 每行包含两个整数 $s_i$ 和 $t_i$   $s_i, t_i le 10^5)$ , 代表一组询问.

输出描述

对于每组数据, 输出一个整数 $S=(displaystylesum_{i=1}^{m} i cdot z_i) ext{ mod } (10^9 + 7)$ , 其中 $z_i$ 是第 $i$ 次询问的答案.

输入样例

输出样例

Hint

 $3 \to 4$  (2次操作):  $3 \to 7 \to 4$ 

 $1 \to 2$  (1次操作):  $1 \oplus 3 = 2$ 

 $3 \to 9$  (2次操作):  $3 \to 1 \to 9$

/*
hdu 5637	

给你n个数，然后对于x有两种操作：
1.改变x二进制中的一位，即1->0 or 0->1
2.将x与n个数中的t异或得到 x^t
求最后得到y的最小操作数

最开始想到求出x^y，但是不知道怎么处理。如果每个询问都进行一次搜索的话感觉
会TLE,为什么就没想到预处理出来- -！

正解：
先把上面两种操作得到所有情况求出来，然后从x->y也就是异或上(x^y)，而这个值
的最小步数已经处理出来，直接进行O(1)的查询即可

hhh-2016-03-06 12:12:08
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int maxn=100500;
const int MOD = 1e9+7;

int a[maxn];
int step[maxn<<2];
int tp[maxn<<2];
int y,n;
int ans ;

void bfs()
{
    memset(step,-1,sizeof(step));
    int star = 0,tail = 0;
    tp[0] = 0,step[0] = 0;
    while(star <= tail)
    {
        int cur = tp[star];
        for(int i =1; i <= n;i++)
        {
            int t = cur^a[i];
            if(step[t] != -1)
                continue;
            tp[++tail] = t;
            step[t] = step[cur]+1;
        }
        for(int i =0;i <= 17;i++)
        {
            int t = cur^(1<<i);
            if(step[t] != -1)
                continue;
            tp[++tail] = t;
            step[t] = step[cur]+1;
        }
        star++;
    }
    return ;
}


int main()
{
    int t,q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&q);
        for(int i =1; i <= n; i++)
        {
            scanf("%d",&a[i]);
        }
        bfs();
        int x,y;
        ll sum = 0;
        for(int i = 1;i <= q;i++)
        {
            scanf("%d%d",&x,&y);
            int ans = step[x^y];
            sum = (sum+(ll)(i*ans)%MOD)%MOD;
        }
        printf("%I64d
",sum%MOD);

    }
    return 0;
}