牛客多校第二场 C 题题解

C Link with Nim Game

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

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

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

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

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

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

之所以不考虑 $00$ 是因为 $00$ 不会影响到减一对 $\mathrm{l}\mathrm{o}\mathrm{w}\mathrm{b}\mathrm{i}\mathrm{t}\backslash 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;
}