結果
問題 |
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 |
ソースコード
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)