HDU 5637 Transform

Problem Description

n integers are given. For an integer 

x you can do the following operations:

+ let the binary representation of 

x be 

b31b30...b0¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯, you can flip one of the bits.

+ let 

y be an integer in the list, you can change 

x to 

x⊕y, where 

⊕ 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

T 

(T≤20), indicating the number of test cases. For each test case:

The first line contains two integer 

n and 

m 

(1≤n≤15,1≤m≤105) -- the number of integers given and the number of queries. The next line contains 

nintegers 

a1,a2,...,an 

(1≤ai≤105), separated by a space.

In the next 

m lines, each contains two integers 

si and 

ti 

(1≤si,ti≤105), denoting a query.

Output

S=(∑i=1mi⋅zi) mod (109+7), where 

zi is the answer for 

i-th query.

Sample Input

1

3 3

1 2 3

3 4

1 2

3 9

Sample Output

Hint

最近一直在做pat，做的人都水了，竟然想着暴力能過。。這題可以直接預處理處理所有的狀态，然後直接o（1）回答就好了。

#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<map>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 4e4;
int T, n, m, ans;
int a[20], f[maxn], x, y;
bitset<20> t;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d", &n, &m);    
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    memset(f, 1, sizeof(f));
    queue<int> p; p.push(f[0] = 0);
    while (!p.empty())
    {
      int q = p.front();  p.pop();
      for (int i = 0; i < n; i++)
      {
        if (f[q^a[i]]>f[q] + 1)
        {
          f[q^a[i]]=f[q] + 1;
          p.push(q^a[i]);
        }
      }
      for (int i = 0; i < 17; i++)
      {
        if (f[q^(1<<i)]>f[q] + 1)
        {
          f[q ^ (1 << i)] = f[q] + 1;
          p.push(q ^ (1 << i));
        }
      }
    }
    int res = 0;
    for (int k = 1; k <= m; k++)
    {
      scanf("%d%d", &x, &y);
      (res += k*f[x^y]) %= mod;
    }
    printf("%d\n", res);
  }
  return 0;
}