結果

問題 No.1240 Or Sum of Xor Pair
ユーザー betrue12
提出日時 2020-09-26 00:16:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,620 ms / 2,000 ms
コード長 1,590 bytes
コンパイル時間 1,876 ms
コンパイル使用メモリ 200,964 KB
最終ジャッジ日時 2025-01-14 21:47:19
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
struct BinaryTrie{
    int nth_bit(int64_t x, int n){ return (x>>n) & 1; }

    struct Node{
        Node* ch[2];
		vector<vector<int>> num;
        Node(){
			ch[0] = ch[1] = nullptr;
			num = vector<vector<int>>(18, vector<int>(2));
		}
    };

    int B;
    Node* root;

    BinaryTrie(int B=0){ if(B) initialize(B); }
    void initialize(int inB){
        B = inB;
        root = new Node();
    }

    void insert(Node* node, int x, int depth){
		for(int k=0; k<18; k++) node->num[k][nth_bit(x, k)]++;
        if(depth < B){
            int nextdepth = depth + 1;
            int nextbit = nth_bit(x, B - nextdepth);
            if(!node->ch[nextbit]) node->ch[nextbit] = new Node();
            insert(node->ch[nextbit], x, nextdepth);
        }
    }
    void insert(int x){ insert(root, x, 0); }

	void calc(Node* node, int x, int now, int K, int X, int64_t& ans){
		if(!node) return;
		int mn = now, mx = now + (1LL<<K) - 1;
		if(mn >= X) return;
		if(mx < X){
			for(int k=0; k<18; k++) for(int t=0; t<2; t++) ans += node->num[k][t] * (1LL<<k) * (nth_bit(x, k) | t);
			return;
		}
		if(K > 0) for(int t=0; t<2; t++) calc(node->ch[t], x, now + (1LL<<(K-1)) * (nth_bit(x, K-1) ^ t), K-1, X, ans);
	}

	void calc(int x, int X, int64_t& ans){ return calc(root, x, 0, B, X, ans); }
};
 
int main(){
	int N, X;
	cin >> N >> X;
	BinaryTrie bt(18);
	vector<int> A(N);
	for(int i=0; i<N; i++){
		cin >> A[i];
		bt.insert(A[i]);
	}

	int64_t ans = 0;
	for(int a : A){
		ans -= a;
		bt.calc(a, X, ans);
	}
	ans /= 2;
	cout << ans << endl;
}
0