Saiko~ No Contesuto #01 : わくわく排他的論理和

面白かったです。
https://www.hackerrank.com/contests/camypapercon01/challenges/exciting-xor

問題

以下のクエリがT個与えられるので、それぞれ答えよ。

各クエリはK,L,Rの３整数からなる。
[L..R]の範囲の整数を(重複あり等確率で)K個選びxorを取った値の期待値を求めよ。

解法

[L..R]の範囲の整数を１個選んだ時、２進数のd桁目が1である確率をpとする。

n個整数を取ってxorを取ったとき、２進数のd桁目が1である確率をf(d,n)とすると、f(d,0)=0, f(d,n)=p*(1-f(d,n-1))+(1-p)*f(d,n-1) = (1-2*p)*f(d,n-1) + pとなる。
f(d,K)の求め方としては、漸化式を行列表現して行列累乗に持ち込む方法と、ダブリングの要領で処理する必要がある。
今回のコードは行列累乗を使ってしまったが、ダブリングの方がシンプル。後者は下記問題を参考。
CODE FESTIVAL 2014 あさプロHard : A - eject - kmjp's blog

f(d,K)が求まったら、(2^d)*f(d,K)を答えに加算する。
上記処理を(2進数の)各桁について行えばよい。

注意点として、この解法だとdoubleでf(d,K)を求めると誤差によりWAとなるケースがある。
C++ならlong doubleを使えば問題ないようだ。

vector<ll> bitnum(ll L,ll R=-1) {
	if(R==-1) R=L,L=0;
	else L--;
	
	vector<ll> r;
	for(int i=0;i<=62;i++) {
		ll step=1LL<<i;
		r.push_back((R/(2*step)*step) + max(0LL,(R%(2*step))-(step-1)));
		r.back() -= (L/(2*step)*step) + max(0LL,(L%(2*step))-(step-1));
	}
	return r;
}

const int MAT=2;
struct Mat { long double v[MAT][MAT]; };
Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) r.v[x][y] += (a.v[x][z]*b.v[z][y]);
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

int T;
ll K,L,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K>>L>>R;
		auto v=bitnum(L,R);
		double ret=0;
		FOR(i,31) {
			long double p = v[i]*1.0/(R-(L-1));
			Mat m;
			m.v[0][0]=1-2*p;
			m.v[0][1]=p;
			m.v[1][0]=0;
			m.v[1][1]=1;
			auto m2=powmat(K,m);
			ret += pow(2,i)*m2.v[0][1];
		}
		
		_P("%.12lf\n",ret);
	}
}

まとめ

1日に10^18回、1秒に11.6G回xorを取れるkamipeipaaさんは、最近のマルチコアCPU並に演算が速いようだ。