C++ 解法, 执行用时: 13ms, 内存消耗: 2168KB, 提交时间: 2020-10-31

#include <cstdio>
#include <vector>
using std::vector;
struct Node {
    int next[2], cnt;
    Node() :cnt(0) {
        next[0] = next[1] = -1;
    }
}init;
vector<Node> a(1, init);
void insert(int x) {
    for (int i = 16, index = 0; i >= 0; --i) {
        int& tmp = a[index].next[( x >> i ) & 1];
        if (tmp == -1)tmp = a.size(), a.push_back(init);
        ++a[index = tmp].cnt;
    }
}
int m;
long long ans = 0;
void dfs(int cur, int l, int r) {
    for (int i = 0; i <= 1; ++i) {
        for (int j = 0; j <= 1; ++j) {
            int t1 = a[l].next[i], t2 = a[r].next[j];
            if (l == r && i && !j || t1 == -1 || t2 == -1)continue;
            int tmp = ( i ^ j ) - ( ( m >> cur ) & 1 );
            if (tmp > 0)ans += (long long)a[t1].cnt * a[t2].cnt;
            else if (tmp == 0 && cur)dfs(cur - 1, t1, t2);
        }
    }
}
#define get() getchar_unlocked()-'0'
inline void scan(int &num) {
    do num = get(); while (num < 0 || num > 9);
    for (int c; ( c = get() ) >= 0 && c <= 9; ( num *= 10 ) += c);
}
int main() {
    a.reserve(1 << 18);
    int n; scan(n), scan(m);
    for (int tmp; n--; insert(tmp))scan(tmp);
    dfs(16, 0, 0);
    printf("%lld\n", ans);
    return 0;
}

C++ 解法, 执行用时: 14ms, 内存消耗: 2168KB, 提交时间: 2020-10-31

#include <cstdio>
#include <vector>
using std::vector;
struct Node {
    int next[2], cnt;
    Node() :cnt(0) {
        next[0] = next[1] = -1;
    }
}init;
vector<Node> a(1, init);
void insert(int x) {
    for (int i = 16, index = 0; i >= 0; --i) {
        int& tmp = a[index].next[( x >> i ) & 1];
        if (tmp == -1)tmp = a.size(), a.push_back(init);
        ++a[index = tmp].cnt;
    }
}
int m;
long long ans = 0;
void dfs(int cur, int l, int r) {
    for (int i = 0; i <= 1; ++i) {
        for (int j = 0; j <= 1; ++j) {
            int t1 = a[l].next[i], t2 = a[r].next[j];
            if (l == r && i && !j || t1 == -1 || t2 == -1)continue;
            int tmp = ( i ^ j ) - ( ( m >> cur ) & 1 );
            if (tmp > 0)ans += (long long)a[t1].cnt * a[t2].cnt;
            else if (tmp == 0 && cur)dfs(cur - 1, t1, t2);
        }
    }
}
#define get() getchar_unlocked()-'0'
inline void scan(int &num) {
    do num = get(); while (num < 0 || num > 9);
    for (int c; ( c = get() ) >= 0 && c <= 9; ( num *= 10 ) += c);
}
int main() {
    a.reserve(1 << 18);
    int n; scan(n), scan(m);
    for (int tmp; n--; insert(tmp))scan(tmp);
    dfs(16, 0, 0);
    printf("%lld\n", ans);
    return 0;
}