「Codeforces 15C」Industrial Nim

Description

现在有很多石子，可以分为 $n$ 个区。第 $i$ 个区中有 $m_i$ 堆石子，且这个区的第 $j$ 堆石子共有 $x_i + j - 1$ 个石子。现两个人每次从任意一堆石子中取正整数个石子，取完石子的人获胜，他们都会做出最优的选择。若先手赢输出 “tolik”，后手赢输出 “bolik”（不包含引号）。$(1 \leq n \leq 10^5,1 \leq m_i,x_i \leq 10^{16})$

Source

[Luogu]CF15C

[Codeforces]15C

Solution

很显然这是一个 Nim 游戏，也就是说只要把每一堆中的石子个数异或起来，不为 $0$ 则先手必胜（$\rm SG$ 定理）。

但石子最多可能有 $\sum\limits_{i = 1}^n m_i$ 堆，直接异或会超时，所以要结合每一个区中石子个数的特性。

对于第 $i$ 个区，我们设 $l = x_i,r = x_i + m_i - 1,pre_i = 0 \oplus 1 \oplus 2 \oplus \cdots \oplus i$，那么这个区中每一堆石子个数的异或和为 $pre_r \oplus pre_{l - 1}$ 。

$x_i$ 和 $m_i$ 很大，所以考虑找规律。

首先易证 $a \oplus (a + 1) = 1$，其中 $a \in \{ x \mid x \in {\rm N},x = 2k \}$（因为二进制下 $a$ 的右起第一位为 $0$，而 $a + 1$ 为 $1$，其余二进制位都相同）。

假如我们现在要求 $pre_x$，可以分成 $4$ 种情况：

$x \bmod 4 = 0$，$0 \oplus 1 \oplus 2 \oplus \cdots \oplus (x - 1)$ 可以变为 $\frac{x}{2}$ 个 $1$ 的异或和，且 $\frac{x}{2}$ 一定是一个偶数，所以前 $x - 1$ 个数的异或和为 $0$，$0 \oplus x = x$，此时 $pre_x = x$ 。
$x \bmod 4 = 1$，$0 \oplus 1 \oplus 2 \oplus \cdots \oplus x$ 可以变为 $\frac{x+1}{2}$ 个 $1$ 的异或和，且 $\frac{x+1}{2}$ 一定是一个奇数，所以此时 $pre_x = 1$ 。
$x \bmod 4 = 2$，$0 \oplus 1 \oplus 2 \oplus \cdots \oplus (x - 1)$ 可以变为 $\frac{x}{2}$ 个 $1$ 的异或和，且 $\frac{x}{2}$ 一定是一个奇数，所以前 $x - 1$ 个数的异或和为 $0$，而 $x$ 是偶数，$1 \oplus x = x + 1$，此时 $pre_x = x + 1$ 。
$x \bmod 4 = 3$，$0 \oplus 1 \oplus 2 \oplus \cdots \oplus x$ 可以变为 $\frac{x+1}{2}$ 个 $1$ 的异或和，且 $\frac{x+1}{2}$ 一定是一个偶数，所以此时 $pre_x = 0$ 。

这样就可以在 $O(1)$ 的时间内求出 $pre_x$，总时间复杂度为 $O(n)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n;
LL ans;

inline LL solve(LL x) {//求 0 xor 1 xor 2 xor ... xor x 的值 
    LL res = 0;
    switch (x % 4) {//分四种情况 
        case 0 : { res = x; break; }
        case 1 : { res = 1; break; }
        case 2 : { res = x + 1; break; }
        case 3 : { res = 0; break; }
    }
    return res;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        LL x, m, l, r;
        read(x), read(m);
        l = x, r = x + m - 1;
        ans ^= solve(r) ^ solve(l - 1);//求异或和 
    }
    puts(ans ? "tolik" : "bolik");
    return 0;
}