CFR 742 B. Arpa’s obvious problem and Mehrdad’s terrible solution ( Ad hoc )

Problem - B - Codeforces

題意：
給一個數列 A，和一個數 X。求數列中有多少無序對 ( i, j )，使得 A[ i ] XOR A[ j ] = X。

資料規模：
1 ≤ n ≤ 1e5, 0 ≤ x ≤ 1e5
1 ≤ a[ i ] ≤ 1e5

解法：
只要枚舉 i，就知道要求的另一個數是 X XOR A[ i ]。所以累加 X XOR A[ i ] 的數量，但要記得，若 X XOR A[ i ] = A[ i ]，要扣掉重複算到的自己。最後也不要忘記要求的是無序的，所以要除以排列數 2。

時間 / 空間複雜度：
O( N )

int N, X;
vi A;

void init(){
  cin >> N >> X;
  A = vi( N );
  for( int i = 0; i < N; ++i )
    cin >> A[ i ];
}

int maxa;
vi cnt;

void preprocess(){
  maxa = *max_element( A.begin(), A.end() );
  cnt = vi( 2 * maxa + 1 );
  for( int i = 0; i < N; ++i )
    ++cnt[ A[ i ] ];
}

void solve(){
  ll ans = 0;
  for( int i = 0; i < N; ++i ){
    ans += cnt[ X ^ A[ i ] ];
    if( ( X ^ A[ i ] ) == A[ i ] )
      --ans;
  }
  cout << ans / 2 << endl;
}