Codeforces #15 C Industrial Nim

題目就是跟一般Nim沒甚麼分別，不過本題可以有龐大數量的石子堆。
設有N個大堆，第i個大堆有M[i]個石子堆，每石子堆的石子數量是X[i], X[i]+1, ... X[i]+M[i]-1。
現在兩個大在這N個大堆取石子，問誰會勝出。

不難發現的是答案取決於XOR{XOR{X[i]+j: 0 <= j < M[i]} : 1 <= i <= N}。但X[i]和M[i]都可以是10^16，因此不能直接用枚舉的方法。定義P(N) = XOR{i: 0 <= i <= N}，XOR{X[i]+j: 0 <= j < M[i]}則等價於P[X[i]+M[i]-1] XOR P[X[i]-1]。則每大堆可以O(1)算出Nim-sum。而P[N]則是容易算出的﹕

P[N] = 0 if N = 0 or N%4 = 3
     = N if N % 4 = 0
     = N | 3 if N % 4 = 2
     = 1 otherwise

算法複雜度是O(N)。