牛客多校第二场 C 题题解

C Link with Nim Game

C 题题意：给定 $n$ 堆石子 ${a_{n}}$ 玩 Nim 游戏，若该玩家必输则会尽量拖延时间，否则就会速战速决。问游戏会进行多少轮，并求出先手第一步的方案数。 $n \leq 2\times 10^5$ 。

解法：判定输赢根据异或和是否为零。记 $\oplus a_i=w$ 。

若先手必胜，则先手必然尽量取石子，使得剩余异或和为 $0$ 。对于第 $i$ 堆石子，先手必然需要拿走 $a_i \oplus (a_i-w)$ 个石子，才能使得异或和为 $0$ 。因而先手选择一个最大的 $x=a_i \oplus (a_i-w)$ 作为第一次拿的个数，总轮数就是 $\sum a_i -x+1$ （因为此时变成了后手必输结局，方案数下证），方案数就是有多少个数字满足 $a_i \oplus (a_i-w) = \max(a_j \oplus (a_j-w))$ 。

若先手必输，则必然会进行 $\sum a_i$ 轮——每次选取一个 ${\rm lowbit}$ 最小的数字，记它的 $\rm lowbit$ 为 $v$ ，然后取一个。此时异或值为 $2 v - 1$ 。后手为了保证必胜，需要让异或值回到 $0$ ，但是先手只能同样取 $\rm lowbit$ 也为 $v$ 的数字取一个——取任意 $\rm lowbit$ 更高的数字，都会导致更高位的 $1$ 的变化，使得异或值无法回到 $0$ 。因而只能和对手下对称棋，所以一轮都只能拿一个。

考虑先手必输情况下先手的方案数，只需要让先手取了一个石头之后后手不能取走超过一个石头即可。依次考虑 $a_{i}$ 每一个为 $1$ 的位置 $v$ ，分两种情况——

作为 $\rm lowbit$ 出现。记录一下每一位作为 $\rm lowbit$ 的次数，如果第一步选择该石头，则异或值变化 $2 v - 1$ 。
不作为 $\rm lowbit$ 出现。那么如果别的石头 $j$ 里面有以这一位作为 $\rm lowbit$ 的，那么 $j$ 是不可以选择的——因为后手可以从这里抓取 $2v-{\rm lowbit}(a_i)>1$ 个石头，同样可以做到异或值变化 $2 v - 1$ 。

之所以不考虑 $0$ 是因为 $0$ 不会影响到减一对 $\rm lowbit$ 的传递作用。

#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        vector<long long> a(n);
        long long sum = 0, xorsum = 0;
        for (auto &x : a)
        {
            scanf("%lld", &x);
            sum += x;
            xorsum ^= x;
        }
        if (xorsum)
        {
            long long maximum = 0;
            int way = 0;
            for (auto i : a)
                if (i > (i ^ xorsum))
                {
                    long long now = i - (i ^ xorsum);
                    if (now > maximum)
                    {
                        maximum = now;
                        way = 1;
                    }
                    else if (now == maximum)
                        way++;
                }
            printf("%lld %d\n", sum - maximum + 1, way);
        }
        else
        {
            vector<int> ban(31, 0), cnt(31, 0);
            for (auto i : a)
                for (int j = 30; j >= 0;j--)
                    if ((i >> j) & 1)
                    {
                        if ((1 << j) == (i & (-i)))
                            cnt[j]++;
                        else
                            ban[j] = 1;
                    }
            printf("%lld ", sum);
            int way = 0;
            for (int i = 0; i <= 30;i++)
                if (!ban[i])
                    way += cnt[i];
            printf("%d\n", way);
        }
    }
    return 0;
}