AtCoder Regular Contest 208 (Div. 2)

A - Bitwise OR Game

解题思路比较好猜，有价值的点在于如何证明

首先考虑只有两个元素 $a,b$ 的情况. 考虑其二进制，如果存在 $a_i,b_i$ 均为 $1$ 那么先手必胜；否则如果每一个 $a_i,b_i$ 都最多只有一个 $1$ ，那么后手必胜. 推广后可以猜测：如果所有位置上，要么是 $0$ 个 $1$ ，要么有奇数个 $1$ ，就是后手必胜；否则就是先手必胜.

所以考虑 Nim Game 的条件怎么转化：上述的条件其实可以转化成 $\text{XOR}_i\ a_i=\text{OR}_i\ a_i$

简短证明

待补……

AC Code

#include <bits/stdc++.h>
constexpr int N = 2e5 + 10;

int n, a[N];

void run() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    int odd = 0;
    auto get = [](int v, int i) { return v >> i & 1; };

    int tot = 0;
    for (int b = 0; b <= 60; b++) {
        int cnt = 0, mk = 0;
        for (int i = 1; i <= n; i++) {
            cnt += get(a[i], b);

            if (get(a[i], b) && !mk) {
                tot++;
                mk = 1;
            }
        }
        if (cnt % 2 == 1) odd++;
    }

    if (odd == tot) std::cout << "Bob\n";
    else std::cout << "Alice\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t;
    std::cin >> t;
    while (t--) run();
}

B - Sum of Mod

唉其实也猜得八九不离十了，但是下界和一个关键发现没有推出来，导致没有推出可以二分的性质

我们令 $d_i=a_{i+1}\mod a_i$ ，既然是 $\mod{}$ 那么 $a_i\gt d_i$ . 我们还要猜的一个点是最优情况下 $a_{i+1}=a_i+d_i$ .

证明待补（

所以有了这两点后，我们可以推出 $a_{i}$ 的范围：

a_{i+1}=a_i+d_i\lt a_i+a_i=2a_i\\ \Big\lfloor\frac{a_{i+1}}{2}\Big\rfloor+1\le a_i\le a_{i+1}

在固定 $a_n$ 的情况下，我们可以证明， $a_i=\lfloor\frac{a_{i+1}}{2}\rfloor+1$ 总是可以让 Sum of Mod 取到最大，并且这个 Sum of Mod 随着 $a_n$ 变大而变大.

证明待补（

于是就出现了可以二分的性质：我们固定 $a_n$ 后，计算出 $a_{i}$ 序列，判断 Sum of Mod 是否 $\ge k$ ，是的话，我们把右侧的范围收缩掉；否则把左侧范围给收缩掉.

时间复杂度 $O(n\log n)$ .

AC Code

#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 2e5 + 10;
constexpr ll V = 1e9;

ll n, a[N], k;

bool check(ll c) {
    a[n] = c;
    ll sum = 0;
    for (int i = n - 1; i >= 1; i--) {
        a[i] = a[i + 1] / 2 + 1;
        sum += a[i + 1] - a[i];
    }
    return sum >= k;
}

void run() {
    std::cin >> n >> k;
    ll l = 0, r = V + 1;
    while (l + 1 < r) {
        ll mid = l + ((r - l) >> 1);
        (check(mid) ? r : l) = mid;
    }

    a[n] = r;
    ll tmpk = k;
    for (int i = n - 1; i >= 1; i--) {
        ll rest = std::min(tmpk, a[i + 1] - (a[i + 1] / 2 + 1));
        a[i] = a[i + 1] - rest;
        tmpk -= rest;
    }

    for (int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i == n];
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0), std::cout.tie(0);
    int t = 10;
    std::cin >> t;
    while (t--) run();
}

C - Mod of XOR

思路很巧妙的分类讨论. 我一直在分类讨论 $C,X$ 但应该直接从 $n$ 分类讨论

假设 $C$ 的最高位为 $k$ ，即 $2^k\le C\lt 2^{k+1}$ .

如果 $2^k\le n\lt 2^{k+1}$ 且有解
那么因为最高位的 $k$ 被异或掉了，此时 $n\oplus C\lt n$ ，故 $n\oplus C \mod n=n\oplus C$ ，所以 $X=n\oplus C$ . 即 $n=C\oplus X$ .
如果 $n\lt 2^k$ 且有解
那么