結果

問題 No.1240 Or Sum of Xor Pair
ユーザー lam6er
提出日時 2025-04-16 16:06:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,699 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 308,972 KB
最終ジャッジ日時 2025-04-16 16:13:59
合計ジャッジ時間 9,931 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

class TrieNode:
    __slots__ = ['children', 'count']
    def __init__(self):
        self.children = [None, None]
        self.count = 0

def insert(node, number):
    for bit in reversed(range(18)):
        b = (number >> bit) & 1
        if not node.children[b]:
            node.children[b] = TrieNode()
        node = node.children[b]
        node.count += 1

def query(node, number, X):
    count = 0
    current = node
    for bit in reversed(range(18)):
        if not current:
            break
        a_bit = (number >> bit) & 1
        x_bit = (X >> bit) & 1
        if x_bit:
            if current.children[a_bit]:
                count += current.children[a_bit].count
            current = current.children[1 - a_bit]
        else:
            current = current.children[a_bit]
    return count

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    X = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    
    # Compute total_valid_pairs
    root_total = TrieNode()
    total_valid = 0
    for num in A:
        total_valid += query(root_total, num, X)
        insert(root_total, num)
    
    ans = 0
    for b in range(18):
        # Filter numbers where the b-th bit is unset
        S = []
        for num in A:
            if (num & (1 << b)) == 0:
                S.append(num)
        # Compute count_both_unset for this bit
        root = TrieNode()
        count = 0
        for num in S:
            count += query(root, num, X)
            insert(root, num)
        # Add contribution
        ans += (total_valid - count) * (1 << b)
    print(ans)

if __name__ == "__main__":
    main()
0