POJ-2975, ZOJ-3067 : Nim

問題概要

山の数N(<1000)個のNimが与えられる。勝ちになるような手の選び方が何通りあるか求める問題。

解法

よく知られているし、問題文にも書いてあるがNimはA[i]のxorが0なら負け、そうでなければ勝ちである。つまり自分の手番ではxorが0になるように取らなければならない。X=A[0]^A[1]^..^A[N-1]とする。このとき、A[i]からm個の石をとってxorが0になるようにするには、(A[i]-m)^(X^A[i]) = 0、すなわちA[i]-m = X^A[i] 、m = A[i] - X^A[i]個とればよい。後は1<=m<=A[i]となるようにとれるかどうか、すなわち、A[i]>X^A[i]であればよい。

acceptされたコード

計算量O(N)。

#include <cstdio>
using namespace std;

const int MAX_N = 1000;

int N;
int as[MAX_N];

bool init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}
	return N > 0;
}

int solve(){
	int x = 0;
	for(int i=0; i<N; i++){
		x ^= as[i];
	}

	int ans = 0;
	for(int i=0; i<N; i++){
		if(as[i] > (x ^ as[i])){
			ans++;
		}
	}

	return ans;
}

int main(){
	while(init()){
		printf("%d\n", solve());
	}

	return 0;
}