🥜 | 题解：CF2032F Peanuts

· · 题解

首先需要解决的问题是，给定一个局面，求先手是否必胜。我们发现，组和组之间是独立的，我们只关心每组最后不能操作的人是谁（他将作为下一组的先手）。所以我们可以倒过来求解。如果我们需要抢到先手，那么相当于在这组中必须让对面拿走最后一个物品，否则在这组中必须让自己拿到最后一个物品。这实际上对应了反 Nim 游戏和 Nim 游戏的先手必胜情况。

对于 Nim 游戏的局面 [a_1,a_2,\dots a_k]，我们熟知当 a_1\oplus a_2\oplus \dots \oplus a_k\neq 0 时先手必胜，否则后手必胜。

对于反 Nim 游戏的局面 [a_1,a_2,\dots a_k]，我们熟知当 \forall i,a_i=1 时，若 k 为偶数先手必胜，否则后手必胜；当 \exist i, a_i\neq 1 时，若 a_1\oplus a_2\oplus \dots \oplus a_k\neq 0 先手必胜，否则后手必胜。

那么有一个简单的 \mathcal O(n^2) DP 做法：设 f_{i,0/1} 表示 [i,n] 这段后缀，分成若干组，先手必胜 / 后手必胜的方案数。转移时枚举 [i,j] 分一段，对于 f_{j+1,*}，如果先手必胜，做反 Nim 游戏，否则做 Nim 游戏。容易用前缀和 + 哈希表优化到 \mathcal O(n)，可以通过。注意要把 1 的连续段拿出来特殊处理。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e6+9,Mod=998244353;
ll T,n,a[N],suf[N],nxt[N],dp[N][2],S[2];
unordered_map<ll,ll>mp[2];
ll MP(ll id,ll x){
    if(mp[id].count(x))return mp[id][x];
    return 0;
}
void solve(){
    n=read();
    rep(i,1,n)a[i]=read();
    rep(i,0,n+1)suf[i]=0,dp[i][0]=dp[i][1]=0;
    per(i,n,1)suf[i]=suf[i+1]^a[i];
    mp[0].clear(),mp[1].clear();
    S[0]=S[1]=0;
    per(i,n,1){
        if(!suf[i])dp[i][1]=1;
        else dp[i][0]=1;
        if(a[i]==1){
            ll j=i;
            while(j>1&&a[j-1]==1)j--;
            ll tmp[2][2];memset(tmp,0,sizeof(tmp));
            tmp[0][(i+1)&1]=dp[i+1][0];
            tmp[1][(i+1)&1]=dp[i+1][1];
            per(k,i,j){
                if(!suf[k])dp[k][1]=1;
                else dp[k][0]=1;
                dp[k][0]=(dp[k][0]+S[0]-MP(0,suf[k])+Mod)%Mod;
                dp[k][1]=(dp[k][1]+MP(0,suf[k]))%Mod;
                if(suf[k]!=suf[i+1])dp[k][0]=(dp[k][0]-dp[i+1][0]+Mod)%Mod;
                else dp[k][1]=(dp[k][1]-dp[i+1][0]+Mod)%Mod;
                dp[k][0]=(dp[k][0]+S[1]-MP(1,suf[k])+Mod)%Mod;
                dp[k][1]=(dp[k][1]+MP(1,suf[k]))%Mod;
                if(suf[k]!=suf[i+1])dp[k][0]=(dp[k][0]-dp[i+1][1]+Mod)%Mod;
                else dp[k][1]=(dp[k][1]-dp[i+1][1]+Mod)%Mod;
                dp[k][0]=(dp[k][0]+tmp[0][k&1])%Mod;
                dp[k][1]=(dp[k][1]+tmp[1][k&1])%Mod;
                dp[k][0]=(dp[k][0]+tmp[1][(k&1)^1])%Mod;
                dp[k][1]=(dp[k][1]+tmp[0][(k&1)^1])%Mod;
                tmp[0][k&1]=(tmp[0][k&1]+dp[k][0])%Mod;
                tmp[1][k&1]=(tmp[1][k&1]+dp[k][1])%Mod;
            }
            per(k,i,j){
                mp[0][suf[k]]=(mp[0][suf[k]]+dp[k][0])%Mod;
                mp[1][suf[k]]=(mp[1][suf[k]]+dp[k][1])%Mod;
                S[0]=(S[0]+dp[k][0])%Mod;
                S[1]=(S[1]+dp[k][1])%Mod;
            }
            i=j;
            continue;
        }
        dp[i][0]=(dp[i][0]+S[0]-MP(0,suf[i])+Mod)%Mod;
        dp[i][1]=(dp[i][1]+MP(0,suf[i]))%Mod;
        dp[i][0]=(dp[i][0]+S[1]-MP(1,suf[i])+Mod)%Mod;
        dp[i][1]=(dp[i][1]+MP(1,suf[i]))%Mod;
        mp[0][suf[i]]=(mp[0][suf[i]]+dp[i][0])%Mod;
        mp[1][suf[i]]=(mp[1][suf[i]]+dp[i][1])%Mod;
        S[0]=(S[0]+dp[i][0])%Mod;
        S[1]=(S[1]+dp[i][1])%Mod;
    }
    write(dp[1][0]),putchar('\n');
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    T=read();
    while(T--)solve();
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}