yukicoder : No.1240 Or Sum of Xor Pair

割と典型かな…。
https://yukicoder.me/problems/no/1240

問題

整数列Aと整数Xが与えられる。
要素対(i,j)において、i＜jかつA[i] xor A[j] ＜ Xであるとき、A[i] or A[j]の総和を求めよ。

解法

1つずつ数列の値を見つつ、以下の値を更新したり参照したりする。
C(x,v,b) := 処理済みの要素について、2進数表記でx桁目より上の値がvであるもののうち、x桁目がbの数

今新たな入力Aを得たとする。
Y=A^Xを考えたとき、過去のAのうち、Yとx桁目より上で一致し、x桁目で初めて差が生じたケースを考えよう。
AとX両方でx桁目が1の時、過去のAのうちx桁目が0のものとはxorを取ったものがX未満になるので、C(x,v,b)を使ってx桁目に0,1が何個あるか数え上げる。
その後、C(x,v,b)を更新する。

int N,X,A;
int C[18][1<<18][18][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>X;
	ll ret=0;
	FOR(i,N) {
		cin>>A;
		
		int T[18][2]={};
		
		int V=0;
		if(X==1<<18) {
			FOR(j,18) {
				T[j][0]+=C[17][0][j][0]+C[17][(1<<17)][j][0];
				T[j][1]+=C[17][0][j][1]+C[17][(1<<17)][j][1];
			}
		}
		else {
			
			for(j=17;j>=0;j--) {
				if(A&(1<<j)) {
					if(X&(1<<j)) {
						V|=1<<j;
						FOR(x,18) {
							T[x][0]+=C[j][V][x][0];
							T[x][1]+=C[j][V][x][1];
						}
						V^=1<<j;
					}
					else {
						V^=1<<j;
					}
				}
				else {
					if(X&(1<<j)) {
						FOR(x,18) {
							T[x][0]+=C[j][V][x][0];
							T[x][1]+=C[j][V][x][1];
						}
						V^=1<<j;
					}
				}
			}
		}
		
		FOR(j,18) {
			if(A&(1<<j)) {
				ret+=(T[j][0]+T[j][1])*1LL<<j;
			}
			else {
				ret+=(T[j][1])*1LL<<j;
			}
		}
		
		V=A;
		FOR(j,18) {
			V>>=j;
			V<<=j;
			FOR(x,18) C[j][V][x][(A>>x)&1]++;
		}
	}
	
	cout<<ret<<endl;
}

まとめ

こういうの言葉で説明するの難しいな。