[CF1616H] - Keep XOR Low 的题解

123456xwd / 2024-10-23 / 原文

一道比较神奇的题目，状态显得比较扯淡，但是就是能过！

先建立出 trie 树，设 $dp_u$ 表示以 $u$ 为根的子树内的答案。

但我们发现，若 $x$ 的当前位为 $1$，那么问题就没法根据他的左右子树求解了，怎么办呢。

考虑一个很扯淡的状态，设 $dp_{u,v}$ 表示考虑了 $u,v$ 为根的子树，他的答案。

再设一下 $siz_u$ 表示以 $u$ 为根的子树实际上加入过几个数。

一开始我们就还说搞 $dp_u$，但遇到了 $x$ 当前位数为 0 的情况，我们就递归进入的 $dp_{ls_u,rs_u}$。

并且这样子的话，有一个很好的性质，就是对于 $dp_{u,v}(u\neq v)$，$u,v$ 内是可以互相随便选的！

考虑一下 $dp_{u,v}$ 的转移。

若 $x$ 当前位为 $1$，那么相互之间有限制的只有 $(ls_u,rs_v),(rs_v,ls_u)$，我们递归求解这两个，然后乘起来即可，注意还要保留只选的情况。
若 $x$ 当前位为 $0$，那么由于上面的那个性质，$u$ 的左右儿子是可以随便搭配的，$v$ 的也是同理，而若想要交叉一下，那么只有 $(ls_u,ls_v),(rs_u,rs_v)$ 可以，递归求解即可。

然后对于叶子结点，显然是可以随便选的。

发现我们每次 $dp$ 实际上就是进入他的子树，所以时间为 $\mathcal{O}(n\log V)$。

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define p_b push_back
#define m_p make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls(x) tree[x][0]
#define rs(x) tree[x][1]
#define mid ((l+r)>>1)
#define gcd __gcd
#define lowbit(x) (x&(-x))
using namespace std;
int rd(){
    int x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if (ch=='-') f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>9) write(x/10);
    putchar('0'+x%10);
}
const int N=2e5+5,mod=998244353;

int tot=1,n,x;
int tree[N*30][2],siz[N*30],pw[N];
void insert(int val){
    int u=1;siz[u]++;
    for(int i=29;i>=0;i--){
        int c=((val>>i)&1ll);
        if(!tree[u][c]) tree[u][c]=++tot;
        u=tree[u][c],siz[u]++;
    }
}
void add(int &x,int y){
    x+=y;
    if(x>=mod) x-=mod;
}
int solve(int u,int v,int d){
    if(!u||!v) return pw[siz[u]+siz[v]];
    if(u==v){
        if(d<0) return pw[siz[u]];
        if((x>>d)&1ll) return solve(ls(u),rs(u),d-1);
        else return (solve(ls(u),ls(u),d-1)+solve(rs(u),rs(u),d-1))%mod;
    }
    else{
        if(d<0) return pw[siz[u]+siz[v]];
        if((x>>d)&1ll) return ((solve(ls(u),rs(v),d-1)+1)*(solve(rs(u),ls(v),d-1)+1)%mod-1+mod)%mod;
        else{
            int ans=(solve(ls(u),ls(v),d-1)+solve(rs(u),rs(v),d-1))%mod;
            add(ans,pw[siz[ls(u)]]*pw[siz[rs(u)]]%mod);
            add(ans,pw[siz[ls(v)]]*pw[siz[rs(v)]]%mod);
            return ans;
        }
    }
}

signed main(){
    n=rd();x=rd();
    for(int i=1;i<=n;i++) insert(rd());
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=(pw[i-1]+pw[i-1])%mod;
    for(int i=0;i<=n;i++) add(pw[i],mod-1);
    printf("%lld\n",solve(1,1,29)%mod);
    return 0;
}