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]であればよい。

2011-2012 Waterloo Local Contest, 24 September, 2011 E : Harmonious Matrices

問題概要

ある二次元ボードが調和的であるとは自分を含む5近傍の和がmod 2で0となるときにいう。H*W(H,W<40)の調和的な行列を出力する問題。ただし自明解としてすべて0というのがあるので、非自明解が存在するならば必ず非自明解を出力する。

解法

mod 2での連立1次方程式を解けばよい。このままだとMAX_W^6でTLEするがビット演算を使って高速化すれば通る。埋め込みはファイルが大きくなりすぎるので適切な圧縮が必要。