結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
![]() |
提出日時 | 2024-12-08 17:01:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 190 ms / 3,000 ms |
コード長 | 1,479 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 115,956 KB |
最終ジャッジ日時 | 2024-12-08 17:01:11 |
合計ジャッジ時間 | 7,466 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
def walsh_hadamard_transform(f):k = (len(f) - 1).bit_length()h = 1for _ in range(k):for i in range(0, len(f), h * 2):for j in range(i, i + h):f[j], f[j + h] = f[j] + f[j + h], f[j] - f[j + h]h *= 2def Xor_convolution(a, b):f = a[:]g = b[:]k = (len(f) - 1).bit_length()walsh_hadamard_transform(f)walsh_hadamard_transform(g)for i in range(1 << k):f[i] = f[i] * g[i]walsh_hadamard_transform(f)for i in range(len(f)):f[i] >>= kreturn fN, K = map(int, input().split())A = list(map(int, input().split()))F = [0 for i in range(1 << 15)]for a in A:F[a >> 15] += 1F = Xor_convolution(F, F)F[0] -= Nfor i in range(1 << 15):F[i] //= 2if i > 0:F[i] += F[i - 1]i = 0while F[i] < K:i += 1mask = ians = i << 15if i > 0:K -= F[i - 1]G = [[] for i in range(1 << 15)]for a in A:b = a >> 15G[b].append(a - (b << 15))F = [0 for i in range(1 << 15)]for i in range(1 << 15):c = min(len(G[i]), len(G[mask ^ i]))if c <= 1024:for j in G[i]:for k in G[i ^ mask]:F[j ^ k] += 1else:f, g = [0 for _ in range(1 << 15)], [0 for _ in range(1 << 15)]for j in G[i]:f[j] += 1for k in G[i ^ mask]:g[k] += 1f = Xor_convolution(f, g)for j in range(1 << 15):F[j] += f[j]if mask == 0:F[0] -= Nfor i in range(1 << 15):F[i] //= 2if i > 0:F[i] += F[i - 1]i = 0while F[i] < K:i += 1ans += iprint(ans)