CF2032F Peanuts

首先给个结论：反 nim 游戏（谁取到最后一个谁输）的游戏先手的必胜条件：

1. 当所有数都是 \(1\) 时，数的个数为奇先手必败，否则必胜。
2. 其他情况，所有数异或和为 \(0\) 先手必败，否则必胜。
   设 \(f_{i,0/1}\) 表示前 \(i\) 个，先手取到 / 没取到最后一个的方案数。
   考虑转移。
   枚举 \(j\) 表示上一个块的结尾。

\(f_{i,0}\) 的转移

如果 \(i\) 到 \(j\) 玩 nim 游戏先手必胜，那  Alice 就要当这一块的先手，也就是前一块没取到最后一个，\(f_{i,0}+=f_{j,1}\)。
如果 \(i\) 到 \(j\) 玩 nim 游戏先手必败，那  Alice 就要当这一块的后手，也就是前一块取到最后一个，\(f_{i,0}+=f_{j,0}\)。

\(f_{i,1}\) 的转移

如果 \(i\) 到 \(j\) 玩反 nim 游戏先手必胜，那  Alice 就要当这一块的先手，也就是前一块没取到最后一个，\(f_{i,1}+=f_{j,1}\)。
如果 \(i\) 到 \(j\) 玩反 nim 游戏先手必败，那  Alice 就要当这一块的后手，也就是前一块取到最后一个，\(f_{i,1}+=f_{j,0}\)。
这样，就得到了 \(\mathcal{O}(n^2)\) 的做法。

\(\mathcal{O}(n^2)\) 代码

#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=1000010,mod=998244353;
int n,a[maxn],f[maxn][2];
void solve(){
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]^=a[i-1],f[i][0]=f[i][1]=0;
    f[0][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[i]^a[j]) f[i][0]=(f[i][0]+f[j][1])%mod;
            else f[i][0]=(f[i][0]+f[j][0])%mod;
        }
        bool ff=1;
        for(int j=i;j>=1;j--){
            if((a[j]^a[j-1])!=1) ff=0;
            if(ff){
                if(i-j+1&1) f[i][1]=(f[i][1]+f[j-1][0])%mod; 
                else f[i][1]=(f[i][1]+f[j-1][1])%mod;
            }
            else{
                if(a[i]^a[j-1]) f[i][1]=(f[i][1]+f[j-1][1])%mod;
                else f[i][1]=(f[i][1]+f[j-1][0])%mod;
            }
        }
    }
    write(f[n][0]);
}
signed main(){
    int T;read(T);
    while(T--) solve(),write("\n");
    return 0;
}

但是这样会 \(TLE\)。考虑优化。
对于 \(f_{i,0}\) 的转移，用一个桶维护一下即可。
对于 \(f_{i,1}\) 的转移，用一个桶维护前面的信息，末尾连续的 \(1\) 另开一个数组存。

代码

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define int long long
const int maxn=1000010,mod=998244353;
int n,a[maxn],f[maxn][2],h,hh,w[2][2];
__gnu_pbds::gp_hash_table<int,int>mp[2],mp2[2];
void solve(){
    mp[0].clear(),mp[1].clear();
    mp2[0].clear(),mp2[1].clear();
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]^=a[i-1],f[i][0]=f[i][1]=0;
    f[0][1]=1;
    mp[1][a[0]]=1;
    h=1;
    hh=0;
    w[0][0]=w[1][0]=w[1][1]=0;
    w[0][1]=1;
    int wz=0;
    for(int i=1;i<=n;i++){
        f[i][0]=(h-mp[1][a[i]]+mp[0][a[i]]+mod)%mod;
        if((a[i]^a[i-1])>1){
            while(wz<i){
                (mp2[0][a[wz]]+=f[wz][0])%=mod;
                (mp2[1][a[wz]]+=f[wz][1])%=mod;
                (hh+=f[wz][1])%=mod;
                wz++;
            }
            w[0][0]=w[0][1]=w[1][0]=w[1][1]=0;
        }
        f[i][1]=(hh-mp2[1][a[i]]+mp2[0][a[i]]+mod)%mod;
        f[i][1]=(f[i][1]+w[!(i&1)][0]+w[i&1][1])%mod;
        (mp[0][a[i]]+=f[i][0])%=mod;
        (mp[1][a[i]]+=f[i][1])%=mod;
        (h+=f[i][1])%mod;
        (w[i&1][0]+=f[i][0])%=mod;
        (w[i&1][1]+=f[i][1])%=mod;
    }
    write(f[n][0]);
}
signed main(){
    int T;read(T);
    while(T--) solve(),write("\n");
    return 0;
}