题解归档 - cf2239A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2239A
• 本地来源：problems/cf2239A/idea.md
• 题目链接：https://codeforces.com/contest/2239/problem/A
• 原始标题：cf2239A - Nim Game Is XOR Game

思路

cf2239A - Nim Game Is XOR Game

pattern

game_sg, invariant_mod_parity, xor.

claim

A state is losing iff it has at most one positive pile.

If at most one pile is positive, every legal b can only have that one nonzero coordinate, so xor(b)=0 forces b=0, which is not legal.

If at least two piles are positive, let X be the xor of all piles. If X=0, choose b=a and move to all zero. If X!=0, take a pile whose highest set bit of X is set; then X xor a_i < a_i. Set all other target piles to zero and leave pile i as a_i-(X xor a_i). The removed vector has xor zero, so this moves to a losing state.

necessary

Alice's first move must leave a losing state, hence at most one positive pile.

sufficient

Every move counted by the formula leaves such a losing state, so Bob has no winning reply from the resulting P-position.

count

For target all zero: valid iff xor(a)=0.

For target with only pile i positive: all other removed values are fixed as a_j; the removed value at i must be xor_except_i = xor(a) xor a_i. This gives one valid target iff xor_except_i < a_i.

Special case n=1: there is no nonzero vector with xor zero, answer is zero.

brute/check

Small states can be verified by full game DP over all vectors and enumerating all legal zero-xor removals. The submitted formula was stress-checked against this DP for small random cases.

edge

xor(a)=0, n=1, equal piles, exactly two positive piles after moves, maximum a_i < 2^30.

代码

来源：problems/cf2239A/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const ll maxn=1e6;
ll s[maxn+5];
int main(){
    ll t,n,i,j,k,dq,ans,zc;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        dq=0;
        for(i=1;i<=n;i++){
            scanf("%lld",&s[i]);
            dq^=s[i];
        }
        if(n==1){
            printf("0\n");
            continue;
        }
        ans=(dq==0);
        for(i=1;i<=n;i++){
            zc=dq^s[i];
            if(zc<s[i]) ans++;
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}