C. Link with Nim Game

Solution

根据nim博弈，对于先手必胜的情况，每次只需要拿走若干石子后异或和是0即可；先手必败的情况，为了使得拿的次数最多，每次只拿一个且让对手也只拿一个是最优的。
比较难算一点的是第一步可选的方案数，对于先手必胜的情况，记$ss$为所有石子的异或和，则对于每堆石子可以计算能拿的石子数量$x=a[i]-s\oplus a[i]x=a[i]\; -\; s\backslash oplus\; a[i]$，取max并记录最大值个数即可。
对于先手必败的情况，考虑拿一个石子对异或和的影响是使得从$0lowbit(a[i])0~lowbit(a[i])$的所有二进制位都变为1，这里就需要其他堆的石子满足：要么无法取石子使得异或和重新变为0，要么只能取一个使得异或和重新变为0。
无法取石子使得异或和重新变为0，就是要使得其石子数量在$lowbit(a[i])lowbit(a[i])$位是0，这样异或之后就会使得其变大，算出的$xx$是负数；只能取一个使得异或和重新变为0，就是石子数量的$lowbitlowbit$必须等于$lowbit(a[i])lowbit(a[i])$。
因此，考虑将所有石子堆按lowbit排序，记录前缀后缀的或和，对于lowbit相同的一段，查询其他石子堆在$lowbitlowbit$处是否全为0。
时间复杂度$O(n\log n)O(n\backslash log\; n)$。

int a[N], pre[N], suf[N];
bool cmp(int x, int y) {
    return lowbit(x) < lowbit(y);
}

int main() {
    int T = fast_IO::read();
    while (T--) {
        int n = fast_IO::read(), s = 0;
        ll sum = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = fast_IO::read();
            sum += a[i];
            s ^= a[i];
        }
        if (s == 0) {
            int ans = 0;
            sort(a + 1, a + n + 1, cmp);
            for (int i = 1; i <= n; ++i)pre[i] = pre[i - 1] | a[i];
            suf[n + 1] = 0;
            for (int i = n; i; --i)suf[i] = suf[i + 1] | a[i];
            for (int i = 1; i <= n; ++i) {
                int j = i;
                while (j < n && lowbit(a[j + 1]) == lowbit(a[i]))++j;
                if (!((pre[i - 1] / lowbit(a[i])) & 1) && !(((suf[j + 1] / lowbit(a[i])) & 1)))
                    ans += j - i + 1;
                i = j;
            }
            printf("%lld %d\n", sum, ans);
            continue;
        }
        int maxn = 0, ans = 1;
        for (int i = 1; i <= n; ++i) {
            if ((a[i] ^ s) > a[i])continue;
            int x = a[i] - (s ^ a[i]);
            if (x > maxn)maxn = x, ans = 1;
            else if (x == maxn)++ans;
        }
        printf("%lld %d\n", sum - maxn + 1, ans);
    }
    return 0;
}