1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-02
 * update_at: 2026-08-02
 */

/* P6824 「EZEC-4」可乐 */
/* 思路（与 index.md 样例图的"贡献覆盖"一致）：在"x 的 01-Trie"上为每个 a_i
 * 打 +1 懒标记——k 位 = 1 时，异或位取 0 的整棵子树打标（严格小于，低位任取），
 * 深入异或位取 1 的分支；k 位 = 0 时只能深入异或位取 0 的分支；走到底的叶子 +1。
 * 最后 DFS 把标记下传，覆盖数最大的叶子就是最佳 x。
 * 01-Trie 复用 rbook 文章《Trie 字典树》模板的结构（tree/Node 为公开成员），
 * 打标与下传都写在模板外部。 */

#include <bits/stdc++.h>
using namespace std;

// 字典树 Trie 模板：插入字符串、判断是否存在、统计前缀出现次数
// 模板参数：ALPHA 字符集大小，OFFSET 字符起点（如 'a'）
// 节点维护 pass(经过次数) 和 end(单词结尾次数)
// 用法：Trie<26,'a'> tr; tr.insert("abc"); tr.contains("abc"); tr.count_prefix("ab");
template <int ALPHA = 26, char OFFSET = 'a'>
struct Trie {
    struct Node {
        array<int, ALPHA> ch{}; // ch[c] 子节点编号，0 为空（根也是 0）
        int pass = 0;           // 经过该节点的字符串个数
        int end = 0;            // 以该节点结尾的完整字符串个数
    };

    vector<Node> tree;          // tree[0] 为根

    Trie() { tree.push_back(Node()); }

    // 插入 s
    void insert(const string &s) {
        int u = 0;
        tree[u].pass++;
        for (char cc : s) {
            int c = cc - OFFSET;
            if (tree[u].ch[c] == 0) {       // 无子节点则新建
                tree[u].ch[c] = (int)tree.size();
                tree.push_back(Node());
            }
            u = tree[u].ch[c];
            tree[u].pass++;
        }
        tree[u].end++;
    }

    // 判断 s 是否完整插入过
    bool contains(const string &s) const {
        int u = 0;
        for (char cc : s) {
            int c = cc - OFFSET;
            if (tree[u].ch[c] == 0) return false;
            u = tree[u].ch[c];
        }
        return tree[u].end > 0;  // 必须作为完整单词结尾
    }

    // 统计以 prefix 为前缀的字符串个数
    int count_prefix(const string &prefix) const {
        int u = 0;
        for (char cc : prefix) {
            int c = cc - OFFSET;
            if (tree[u].ch[c] == 0) return 0;
            u = tree[u].ch[c];
        }
        return tree[u].pass;
    }
};

const int MAXN = 100000 + 5;

int n, k;                   // n 箱可乐，上限 k
int a[MAXN];
int top_bit;                // 最高有效位（k 与所有 a_i 的最大位数 - 1）

Trie<2, '0'> trie;          // x 的 01-Trie：每条根到叶子的路径就是一个可能的 x
vector<int> tag(1, 0);      // tag[u]：节点 u 的懒标记，与 trie.tree 下标对齐

// 确保 u 存在 c 儿子；不存在则新建节点并返回其编号。
// 注意：被打标记的分支即使没有 a_i 走过也要显式建出来，
// 否则 DFS 下传会漏掉只靠祖先标记覆盖的隐式叶子。
int ensure_child(int u, int c) {
    if (trie.tree[u].ch[c] == 0) {
        trie.tree[u].ch[c] = (int)trie.tree.size();
        trie.tree.push_back(Trie<2, '0'>::Node());
        tag.push_back(0);
    }
    return trie.tree[u].ch[c];
}

// 为 a_i 打标记：把能接受 a_i 的所有 x 在 x-Trie 上打 +1
void mark(int x) {
    int u = 0;
    for (int bit = top_bit; bit >= 0; bit--) {
        int ab = (x >> bit) & 1; // a_i 的第 bit 位
        if ((k >> bit) & 1) {
            // k 位 = 1（分水岭）：异或位取 0 的分支（x 位 = ab）整棵严格小于 k → +1
            tag[ensure_child(u, ab)] += 1;
            // 异或位取 1 的分支（x 位 = ab^1）等于 k → 继续深入
            u = ensure_child(u, ab ^ 1);
        } else {
            // k 位 = 0（关卡）：异或位只能取 0（x 位 = ab），只能深入
            u = ensure_child(u, ab);
        }
    }
    tag[u] += 1; // 走到底：异或结果恰好等于 k 的 x 打 +1
}

int best = 0;

// DFS 下传：acc = 从根到 u 的标记累计（每个隐式叶子继承祖先标记）。
// 标记只会增加，所以任意节点 u 的 acc 都是其子树内叶子的覆盖数下界，
// 全局最大 acc 就是最大覆盖数。
void push_down(int u, int acc) {
    acc += tag[u];
    best = max(best, acc);
    if (trie.tree[u].ch[0])
        push_down(trie.tree[u].ch[0], acc);
    if (trie.tree[u].ch[1])
        push_down(trie.tree[u].ch[1], acc);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int m = max(k, *max_element(a + 1, a + n + 1));
    top_bit = 31 - __builtin_clz(m); // m >= 1，最高有效位 = floor(log2(m))

    for (int i = 1; i <= n; i++)
        mark(a[i]);

    push_down(0, 0);
    cout << best << '\n';
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-02
 * update_at: 2026-08-02
 */

/* P6824 「EZEC-4」可乐 —— 静态数组版（对应 index.md 样例图的"贡献覆盖"思路） */
/* 与 main.cpp（rbook 模板版）是同一算法的两种实现：
 *   打标记规则完全相同（k 位=1：异或位取 0 的子树 +1、深入异或位取 1 的分支；
 *   k 位=0：只深入异或位取 0 的分支；走到底的叶子 +1）；
 *   区别：这里 DFS 下传时只结算"实际分配出来的叶子"的覆盖度。
 * 节点用 struct 打包：ch[2]（儿子编号）与 tag（懒标记）放在一起。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const int MAX_BIT = 20;             // a, k <= 1e6 < 2^20，留一位余量
const int MAX_NODE = MAXN * 22 + 5; // 每个数最多新增 21 个节点，2.2M 足够

// 01-Trie 节点：ch[2] 儿子编号（0 为空），tag 懒标记
struct Node {
    int ch[2];
    int tag;
} trie[MAX_NODE];

int node_cnt = 1; // 根节点始终为 1，0 号留作"空儿子"哨兵

// 将 a 针对条件 a ^ x <= k 插入并打懒标记
void insert(int a, int k) {
    int u = 1;
    for (int i = MAX_BIT; i >= 0; --i) {
        int bit_a = (a >> i) & 1;
        int bit_k = (k >> i) & 1;

        if (bit_k == 1) {
            // 1. x 使得异或结果当前位为 0：整棵子树严格小于 k，低位任取，打 tag
            // x 位 = a 位 ^ 异或位(0)；^0 是恒等运算（任何数 ^ 0 不变），
            // 写成 ^0 是为了与下面的 ^1 保持公式对称：x_j = a_i[j] ^ (异或位)
            int branch_less = bit_a ^ 0;
            if (!trie[u].ch[branch_less]) {
                trie[u].ch[branch_less] = ++node_cnt;
            }
            trie[trie[u].ch[branch_less]].tag++;

            // 2. x 使得异或结果当前位为 1：保持前缀相等，继续深入
            int branch_eq = bit_a ^ 1;
            if (!trie[u].ch[branch_eq]) {
                trie[u].ch[branch_eq] = ++node_cnt;
            }
            u = trie[u].ch[branch_eq];
        } else {
            // bit_k == 0：异或结果必须为 0（相等），否则会大于 k
            int branch_eq = bit_a ^ 0;
            if (!trie[u].ch[branch_eq]) {
                trie[u].ch[branch_eq] = ++node_cnt;
            }
            u = trie[u].ch[branch_eq];
        }
    }
    // 叶子节点：精确匹配 a ^ x == k 的情况
    trie[u].tag++;
}

int max_cola = 0;

// DFS 把上层的懒标记瀑布式下推到叶子
void dfs(int u, int current_sum) {
    if (!u) return;

    // 累加当前路径上的 tag
    current_sum += trie[u].tag;

    // 走到实际分配出来的叶子，结算该区域的覆盖度
    if (!trie[u].ch[0] && !trie[u].ch[1]) {
        max_cola = max(max_cola, current_sum);
        return;
    }

    // 继续向下传递
    if (trie[u].ch[0]) dfs(trie[u].ch[0], current_sum);
    if (trie[u].ch[1]) dfs(trie[u].ch[1], current_sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        insert(a, k);
    }

    dfs(1, 0);
    cout << max_cola << '\n';
    return 0;
}