HDOJ 5270 - ZYB loves Xor II

Source

BestCoder Round #44 3問目
HDOJ 5270

問題概要

$2$ つの要素数 $N$ の整数列 $\{A_k\}_{k=1}^N, \{B_k\}_{k=1}^N$ が与えられる.
$N^2$ 個の整数 $A_i+B_j, \;\; i,j=1,2,\ldots,N$ の ${\rm XOR}$ を求める問題.

解法

各ビットについて,その桁が $1$ になるような $A_i+B_j$ が何個あるかを求めていけば良い.
なので,$2^k$ の桁が $1$ になるような $A_i+B_j$ が何個あるかを考える.
$A_i, B_i$ は $2^{k+1}$ 以上の桁は影響しないので,${\rm mod}\ 2^{k+1}$ して,上の桁を消しておく.
また,その後,$\{A_k\}, \{B_k\}$ はそれぞれソートしておく.
そうすると,$A_i+B_j$ の値は範囲 $[0, 2^{k+2})$ の中にある.
よって,$A_i+B_j$ が範囲 $[2^k, 2 \times 2^k)$ および範囲 $[3 \times 2^k, 4 \times 2^k)$ の中にあるパターン数をカウントすれば良いことになる.
それぞれは尺取法でカウントできる.
また,配列 $\{A_k\}, \{B_k\}$ は最初にソートしておいて,上のビットから考えていく.
そうすると,次のビットの処理に移るときは,配列の各要素の $2^k$ のビットを削除した後,マージソートの要領でソートすると,毎回のソートは $O(N)$ でできる.
よって,時間計算量は,$d = \max(A_k, B_k)$として,$O(N \log N + d N)$ 程度.

C++によるスパゲッティなソースコード

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

template<class T> void mergeSort(int As, T A[], int Bs, T B[], T res[]){int i=0,j=0,k=0;while(i<As&&j<Bs)if(A[i]<=B[j])res[k++]=A[i++];else res[k++]=B[j++];while(i<As)res[k++]=A[i++];while(j<Bs)res[k++]=B[j++];}
template<class T> ll counterSumLt(int As, T A[], int Bs, T B[], T val){int i=0,j=Bs;ll r=0;while(i<As){while(j&&A[i]+B[j-1]>=val)j--;if(!j)break;while(i<As&&A[i]+B[j-1]<val)i++,r+=j;}return r;}

char memarr[17000000]; void *mem = memarr;
#define MD 1000000007

int T, N;
ll *A, *B, *tmp;

int main(){
  int i, j, bt;
  int Case = 0;
  ll res, cnt;

  A = (ll*)mem;
  B = A + 111111;
  tmp = B + 111111;
  mem = tmp + 111111;

  reader(&T);
  while(T--){
    reader(&N);
    rep(i,N) reader(A+i);
    rep(i,N) reader(B+i);

    sort(A, A+N);
    sort(B, B+N);
    
    res = 0;
    for(bt=61;bt>=0;bt--){
      cnt = (ll)N*N;
      cnt -= counterSumLt(N, A, N, B, 3*(1LL<<bt));
      cnt += counterSumLt(N, A, N, B, 2*(1LL<<bt));
      cnt -= counterSumLt(N, A, N, B, (1LL<<bt));

      if(cnt % 2) res |= (1LL<<bt);

      rep(i,N) if(A[i]&(1LL<<bt)){
        REP(j,i,N) A[j] ^= (1LL<<bt);
        mergeSort(i, A, N-i, A+i, tmp);
        swap(A, tmp);
        break;
      }
      rep(i,N) if(B[i]&(1LL<<bt)){
        REP(j,i,N) B[j] ^= (1LL<<bt);
        mergeSort(i, B, N-i, B+i, tmp);
        swap(B, tmp);
        break;
      }
    }

    printf("Case #%d: ",++Case);
    writerLn(res);
  }

  return 0;
}

Current time: 2024年03月29日04時44分38秒
Last modified: 2015年06月16日11時51分38秒 (by laycrs)
Tags: Competitive_Programming Hangzhou_Dianzi_University_Online_Judge BestCoder_44 BestCoder_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン: