TopCoder SRM 841 : Div1 Easy Div2 Hard DiceOperation

まさかの初SRM1位＆Highest大幅更新。
https://community.topcoder.com/stat?c=problem_statement&pm=17882

問題

いくつかのダイスがある。
i番のダイスは1～X[i]のうちのいずれかの目を等確率で出す。

これらのダイスを一斉に振ったとき、出た目のxorの期待値を求めよ。

解法

目を2進数表記したとき、0-originで下からd桁目が1になる確率P(d)を求め、(2^d)*P(d)の和を取ればよい。

class DiceOperation {
	public:
	double solve(vector <int> dice) {
		
		double ret=0;
		int i;
		FOR(i,30) {
			double p0=1,p1=0;
			FORR(d,dice) {
				ll b=1LL<<i;
				ll X=d/(2*b)*b;
				ll Y=d/(2*b)*b;
				ll c=d%(2*b);
				if(c&b) {
					X+=b;
					Y+=c-b+1;
				}
				else {
					X+=c+1;
				}
				X--;
				double x=1.0*X/d;
				double y=1.0*Y/d;
				
				double q0=p0*x+p1*y;
				double q1=p1*x+p0*y;
				
				p0=q0;
				p1=q1;
			}
			ret+=p1*(1LL<<i);
		}
		return ret;
	}
}

まとめ

「1～Xのうちd bit目が1になる整数の個数」、ライブラリにしておいた方がいいかなぁ…。