CF1616H Keep XOR Low

Trie 树上进行 01 分治。

感觉之前也考类似的题，于是记一下。

显然按照每一位进行考虑，将 Trie 树建出来。我们设置函数 $f(x,y,i)$ 表示前 $i-1$ 位的限制全部卡满，在 $x$ 节点与 $y$ 节点上分别选取两个子集，两个子集之间的元素满足 $x_i\oplus y_i\le k$，考虑当前位：

第 $i$ 位为 $0$，那么 $x,y$ 必须选取同一侧的子树，即 $f(x_0,y_0,i-1),f(x_1,y_1,i-1)$。再加上 $x,y$ 分别在各自子树之中可以任意选的方案（因为前面的位数都会变成 $0$，对第 $i$ 位就没有限制了）。
第 $i$ 位为 $1$，那么 $x,y$ 选同侧的话，就不需要满足被卡满的限制，不符合我们的定义，我们是一定要卡满的，所以不需要递归下去计算，因为这种情况的贡献会在当前节点产生。而我们需要走 $x,y$ 的异侧。并且容易发现 $f(x_0,y_1),f(x_1,y_0)$ 之间是相互独立的，意思是 $x_0,x_1$ 之间与 $y_0,y_1$ 之间是没有限制的（两个都选相当于走同侧），两种情况的贡献就算在一起了，所以直接就是 $f(x_0,y_1)\times f(x_1,y_0)$。

每个节点只会被计算一次，时间复杂度 $\mathcal O(n\log V)$，其中 $V$ 为值域。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1.5e5+10,K=30,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;int f=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,k;
int tot=1,ch[N<<5][2],si[N<<5];
int p[N];
inline int adj(int x){return x>=mod?x-mod:x;}
inline void insert(int x)
{
    int u=1;si[u]++;
    for(int i=K;~i;i--)
    {
        bool v=x>>i&1;
        if(!ch[u][v])ch[u][v]=++tot;
        si[u=ch[u][v]]++;
    }
}
int solve(int x=1,int y=1,int i=30)
{
    if(!x||!y)return p[si[x]+si[y]];
    if(!(x^y))
    {
        if(!~i)return p[si[x]];
        if(k>>i&1)return solve(ch[x][0],ch[x][1],i-1);
        return adj(solve(ch[x][0],ch[x][0],i-1)+solve(ch[x][1],ch[x][1],i-1)-1);
    }
    if(!~i)return p[si[x]+si[y]];
    if(k>>i&1)return 1ll*solve(ch[x][0],ch[y][1],i-1)*solve(ch[x][1],ch[y][0],i-1)%mod;
    return adj(adj(solve(ch[x][0],ch[y][0],i-1)+solve(ch[x][1],ch[y][1],i-1)-1)+
    adj(1ll*(p[si[ch[x][0]]]-1)*(p[si[ch[x][1]]]-1)%mod+1ll*(p[si[ch[y][0]]]-1)*(p[si[ch[y][1]]]-1)%mod));
    
}
int main()
{
    read(n,k);
    for(int i=1;i<=n;i++)
    {
        int x;
        read(x);
        insert(x);
    }
    p[0]=1;
    for(int i=1;i<=n;i++)p[i]=adj(p[i-1]<<1);
    printf("%d\n",solve()-1);
    return 0;
}