CF Gym102331B Bitwise Xor 题解

Solution

引理：一个集合中异或值最小的数对，出现在把所有元素递增排序后相邻的两个数中。
证明：反证法。假设引理不成立，设此时最小数对为 $(x,y)$ ，且存在 $y'$ 满足 $x< y' < y$ 。考虑极大的二进制位 $k$ ，满足 $x$ 的第 $k$ 位上是 $0$ ， $y$ 的第 $k$ 位上是 $1$ ，从而 $x \oplus y$ 的第 $k$ 位是 $1$ 。
如果 $y'$ 的第 $k$ 位是 $0$ ，那么 $x \oplus y'$ 的第 $k$ 位是 $0$ ，从而 $x \oplus y' < x \oplus y$ 。
如果 $y'$ 的第 $k$ 位是 $1$ ，那么一定存在极大的二进制位 $k'$ ，满足 $y$ 的这一位是 $1$ ， $y'$ 的这一位是 $0$ 。然后用类似的方法讨论也能得到 $x \oplus y' < x \oplus y$ 。

所以我们把所有数递增排序。

设 $f_i$ 为以 $a_i$ 结尾的方案数，显然有转移

f_i = 1+\sum_{j=1 \lor a_i \oplus a_j \ge x}^{i-1} f_j

考虑用 0-1 Trie 优化这个 DP。

把 $f_j$ 挂到 Trie 的叶子上，然后在 Trie 树上跑两步。

$a_i \oplus a_j = x$ 这种情况比较 $\text{Trivial}$ ，并且它的处理方法和 $a_i \oplus a_j > x$ 只能说毫不相关。所以先把这种情况单独拎出来，反正就是一个叶子的贡献。

什么时候能直接贡献一棵子树的所有叶子呢？ $x$ 的当前位为 $0$ 时，直接累加与 $a_i$ 当前位相反的那一棵子树就行，此时一定满足 $a_i \oplus a_j > x$ 。

然后我们就要使得 $a_i \oplus a_j$ 在已经处理的数位上等于 $x$ ，所以如果 $a_i$ 与 $x$ 在当前位相同，我们就往 $0$ 儿子处找，否则就往 $1$ 儿子处找。

1
// Problem: B. Bitwise Xor
2
// Contest: Codeforces - 2019 Summer Petrozavodsk Camp, Day 2: 300iq Contest 2 (XX Open Cup, Grand Prix of Kazan)
3
// URL: https://codeforces.com/gym/102331/problem/B
4
// Author: yozora0908
5
// Memory Limit: 1024 MB
6
// Time Limit: 2000 ms
7
//
8
// Let's Daze
9
//
10
// Powered by CP Editor (https://cpeditor.org)
11

12
#include<bits/stdc++.h>
13
using namespace std;
14
#define int long long
15
#define uint unsigned long long
16
#define PII pair<int,int>
17
#define MP make_pair
18
#define fi first
19
#define se second
20
#define pb push_back
21
#define eb emplace_back
22
#define SET(a,b) memset(a,b,sizeof(a))
23
#define CPY(a,b) memcpy(a,b,sizeof(b))
24
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
25
#define per(i,j,k) for(int i=(j);i>=(k);--i)
26
int read() {
27
    int a=0, f=1; char c=getchar();
28
    while(!isdigit(c)) {
29
        if(c=='-') f=-1;
30
        c=getchar();
31
    }
32
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
33
    return a*f;
34
}
35
const int N=3e5+5, mod=998244353;
36
int n, k, a[N];
37
int f[N];
38
struct Trie {
39
    int tot=1, trie[N*60][2], g[N*60];
40
    void insert(int S,int v) {
41
        int x=1;
42
        for(int i=59;~i;--i) {
43
            int a=(S>>i)&1;
44
            if(!trie[x][a]) trie[x][a]=++tot;
45
            x=trie[x][a];
46
            (g[x]+=v)%mod;
47
        }
48
    }
49
    int query(int S) {
50
        int x=1, res=0;
51
        for(int i=59;~i;--i) {
52
            int a=(k>>i)&1, b=(S>>i)&1;
53
            if(a==0) (res+=g[trie[x][b^1]])%=mod;
54
            x=trie[x][a^b];
55
        }
56
        if(x) (res+=g[x])%=mod;
57
        return res;
58
    }
59
} T;
60
signed main() {
61
    n=read(), k=read();
62
    rep(i,1,n) a[i]=read();
63
    sort(a+1,a+n+1);
64
    f[1]=1;
65
    T.insert(a[1],f[1]);
66
    rep(i,2,n) {
67
        int D=T.query(a[i]);
68
        f[i]=(1+D)%mod;
69
        T.insert(a[i],f[i]);
70
    }
71
    int ans=0;
72
    rep(i,1,n) (ans+=f[i])%=mod;
73
    printf("%lld\n",ans);
74
    return 0;
75
}

Nanami^2

Solution

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

Solution

觉得这篇文章怎么样？

分享这篇文章

评论区