Codeforces #189 Div1. A. Malek Dance Club

CF#189は不参加回でした。
http://codeforces.com/contest/319/problem/A

問題

N桁の二進数Xを考える。

0～2^N-1からなる2^N個の数値から2つi,jを抜き出したとき、i j xor Xとなる組み合わせを答えよ。

解答

iとjの先頭p桁が一致し、(p+1)桁目が不一致だとする。
xのp+1桁目が1なら、i xor X > j xor Xとなる。
この時の組み合わせは、先頭p桁がiとjで一致するパターンが2^p通り、(p+2)～N桁目はiとjはなんでもよいので2^(2N-2(p+1) )、合わせて2^(2N-p-2)通り。

各pについて2^(2N-p-2)を加算していけばよい。

void solve() {
	int f,r,i,j,k,l, x,y;
	ll n2[201];
	string X;
	
	n2[0]=1;
	FOR(i,200) n2[i+1]=(n2[i]*2)%1000000007;
	
	cin >> X;
	ll ret=0;
	FOR(i,X.size()) {
		if(X[i]=='1') ret = (ret + n2[i]*n2[2*(X.size()-i-1)]) % 1000000007;
	}
	cout << ret << endl;
}

まとめ

ここらへんはまだ簡単だね。