面白かったです。
https://www.hackerrank.com/contests/camypapercon01/challenges/exciting-xor
問題
以下のクエリがT個与えられるので、それぞれ答えよ。
各クエリはK,L,Rの3整数からなる。
[L..R]の範囲の整数を(重複あり等確率で)K個選びxorを取った値の期待値を求めよ。
解法
[L..R]の範囲の整数を1個選んだ時、2進数のd桁目が1である確率をpとする。
n個整数を取ってxorを取ったとき、2進数の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並に演算が速いようだ。