結果

問題 No.1240 Or Sum of Xor Pair
コンテスト
ユーザー 已经死了
提出日時 2025-10-02 23:41:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,342 bytes
コンパイル時間 255 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 82,664 KB
最終ジャッジ日時 2025-10-02 23:41:58
合計ジャッジ時間 12,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 2 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=lambda:sys.stdin.readline().rstrip("\r\n")
MI=lambda:map(int,input().split())
li=lambda:list(MI())
ii=lambda:int(input())

n,limt=li()
arr=li()

B=9
M=1<<B
mask=M-1

cnt=[[0]*M for _ in range(M)]     # cnt[x][y]: 高B位=x, 低B位=y 的出现次数
cnt2=[[0]*B for _ in range(M)]    # cnt2[x][i]: 高B位=x 时, 低位第i位为1的出现次数
cnt3=[0]*M                        # cnt3[x]: 高B位=x 的出现次数

hi=limt>>B
lo=limt&mask

res=0
pow2=[1<<i for i in range(B)]

for a in arr:
    x=a>>B
    y=a&mask

    # 情况1: (x^nx)<hi
    # 只需枚举 t in [0,hi), nx = x^t
    for t in range(hi):
        nx=x^t
        c=cnt3[nx]
        if c:
            tmp=((x|nx)<<B)
            res+=(tmp+y)*c
            # 低位 y|ny 的贡献 = c*y + 对于 y 的0位把该位的1计数补上
            for i in range(B):
                if (y>>i)&1==0:
                    res+=pow2[i]*cnt2[nx][i]

    # 情况2: (x^nx)==hi 且 (y^ny)<lo
    nx=x^hi
    if 0<=nx<M:
        tmp=((x|nx)<<B)
        # 同理只枚举 t in [0,lo), ny = y^t
        for t in range(lo):
            ny=y^t
            c=cnt[nx][ny]
            if c:
                res+= (tmp + (y|ny)) * c

    # 把当前数加入统计
    cnt[x][y]+=1
    for i in range(B):
        if (y>>i)&1:
            cnt2[x][i]+=1
    cnt3[x]+=1

print(res)
0