yukicoder : No.524 コイン

ライブラリ持ってたので一瞬でした…。
http://yukicoder.me/problems/no/524

問題

正整数Nが与えられる。
石が1,2,3,...N個ある計N個の山でNimを行うとき、勝者は先手後手どちらか。

解法

0～Nのxorを取った値が0かどうかを判定すればよい。
0～Nのxorの求め方だが、各ビットがどうなるか見ていく。

• 最下位ビット
  • 0～Nの最下位ビットのxorは、N=0から順に001100110011...と4毎の周期で変わることがわかるので容易に求められる。
• 最下位ビット以外
  • 下からk bit目に注目する。0,1,2,...についてビットの値は0が2^(k-1)個、1が2^(k-1)個、の順で繰り返す。
  • よって0～Nのxorを取ったときxorが1になる条件はNにおいてこのビットが立っており、かつ最下位ビットが0の場合である。

ll N;

ll xorxor(ll val) {
	int i;
	ll ret=((val+1)/2)%2;
	for(i=0;i<=59;i++) if((val>>i)%2) ret |= (1^(val%2))<<i;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	if(xorxor(N)) cout<<"O"<<endl;
	else cout<<"X"<<endl;
	
}

まとめ

0～Nのxorを取るライブラリを昔作っておいてよかった。