結果
問題 | No.1240 Or Sum of Xor Pair |
ユーザー | vwxyz |
提出日時 | 2023-12-16 05:22:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,651 ms / 2,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 258,764 KB |
最終ジャッジ日時 | 2023-12-16 05:23:29 |
合計ジャッジ時間 | 52,973 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,318 ms
246,164 KB |
testcase_01 | AC | 1,320 ms
246,164 KB |
testcase_02 | AC | 1,328 ms
246,164 KB |
testcase_03 | AC | 1,518 ms
250,436 KB |
testcase_04 | AC | 1,484 ms
250,436 KB |
testcase_05 | AC | 1,461 ms
248,472 KB |
testcase_06 | AC | 1,442 ms
248,348 KB |
testcase_07 | AC | 1,455 ms
248,348 KB |
testcase_08 | AC | 1,460 ms
248,348 KB |
testcase_09 | AC | 1,445 ms
248,344 KB |
testcase_10 | AC | 1,472 ms
253,368 KB |
testcase_11 | AC | 1,484 ms
253,924 KB |
testcase_12 | AC | 1,478 ms
254,112 KB |
testcase_13 | AC | 1,496 ms
255,512 KB |
testcase_14 | AC | 1,507 ms
254,120 KB |
testcase_15 | AC | 1,623 ms
258,732 KB |
testcase_16 | AC | 1,620 ms
258,732 KB |
testcase_17 | AC | 1,631 ms
258,732 KB |
testcase_18 | AC | 1,599 ms
258,736 KB |
testcase_19 | AC | 1,623 ms
258,748 KB |
testcase_20 | AC | 1,626 ms
258,736 KB |
testcase_21 | AC | 1,601 ms
258,736 KB |
testcase_22 | AC | 1,628 ms
258,732 KB |
testcase_23 | AC | 1,635 ms
258,736 KB |
testcase_24 | AC | 1,629 ms
258,732 KB |
testcase_25 | AC | 1,633 ms
258,732 KB |
testcase_26 | AC | 1,651 ms
258,732 KB |
testcase_27 | AC | 1,327 ms
246,164 KB |
testcase_28 | AC | 1,301 ms
246,164 KB |
testcase_29 | AC | 1,540 ms
258,684 KB |
testcase_30 | AC | 1,472 ms
257,936 KB |
testcase_31 | AC | 1,428 ms
257,936 KB |
testcase_32 | AC | 1,493 ms
258,764 KB |
ソースコード
import sys readline=sys.stdin.readline def Hadamard(polynomial,n,mod=0,inverse=False): polynomial_=[x for x in polynomial]+[0]*((1<<n)-len(polynomial)) for bit in range(n): for i in range(1<<n): ii=i^(1<<bit) if i>ii: continue polynomial_[i],polynomial_[ii]=polynomial_[i]+polynomial_[ii],polynomial_[i]-polynomial_[ii] if mod: polynomial_[i]%=mod polynomial_[ii]%=mod if inverse: if mod: inve_2=pow((mod+1)//2,n) for i in range(1<<n): polynomial_[i]*=inve_2 polynomial_[i]%=mod else: pow_2=pow(2,n) for i in range(1<<n): polynomial_[i]//=pow_2 return polynomial_ def XOR_Convolution(polynomial0,polynomial1,mod=0): n=(max(len(polynomial0),len(polynomial1))-1).bit_length() Hadamard_polynomial0=Hadamard(polynomial0,n,mod=mod) Hadamard_polynomial1=Hadamard(polynomial1,n,mod=mod) if mod: convolution=[x*y%mod for x,y in zip(Hadamard_polynomial0,Hadamard_polynomial1)] else: convolution=[x*y for x,y in zip(Hadamard_polynomial0,Hadamard_polynomial1)] convolution=Hadamard(convolution,n,mod=mod,inverse=True) return convolution N,X=map(int,readline().split()) A=list(map(int,readline().split())) M=18 ans=0 C=[[0]*(1<<M) for m in range(M+1)] for a in A: C[M][a]+=1 for m in range(M): if a&1<<m: C[m][a]+=1 for m in range(M+1): C[m]=Hadamard(C[m],M) for bit in range(1<<M): C[m][bit]**=2 C[m]=Hadamard(C[m],M,inverse=True) for x in range(X): for m in range(M): if x&1<<m: ans+=C[M][x]<<m else: ans+=C[m][x]<<m for a in A: ans-=a ans//=2 print(ans)