結果
問題 | No.184 たのしい排他的論理和(HARD) |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-15 15:11:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 195 ms / 5,000 ms |
コード長 | 3,506 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 81,712 KB |
実行使用メモリ | 96,728 KB |
最終ジャッジ日時 | 2023-10-18 12:24:47 |
合計ジャッジ時間 | 6,135 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 66 ms
68,116 KB |
testcase_01 | AC | 66 ms
68,116 KB |
testcase_02 | AC | 65 ms
68,116 KB |
testcase_03 | AC | 66 ms
68,116 KB |
testcase_04 | AC | 66 ms
68,116 KB |
testcase_05 | AC | 66 ms
68,116 KB |
testcase_06 | AC | 66 ms
68,116 KB |
testcase_07 | AC | 66 ms
68,116 KB |
testcase_08 | AC | 157 ms
89,476 KB |
testcase_09 | AC | 99 ms
78,412 KB |
testcase_10 | AC | 140 ms
84,760 KB |
testcase_11 | AC | 123 ms
82,492 KB |
testcase_12 | AC | 170 ms
93,816 KB |
testcase_13 | AC | 181 ms
94,452 KB |
testcase_14 | AC | 134 ms
84,552 KB |
testcase_15 | AC | 190 ms
96,496 KB |
testcase_16 | AC | 167 ms
92,108 KB |
testcase_17 | AC | 175 ms
94,292 KB |
testcase_18 | AC | 65 ms
68,376 KB |
testcase_19 | AC | 65 ms
68,116 KB |
testcase_20 | AC | 101 ms
89,620 KB |
testcase_21 | AC | 187 ms
96,700 KB |
testcase_22 | AC | 194 ms
96,728 KB |
testcase_23 | AC | 65 ms
68,116 KB |
testcase_24 | AC | 64 ms
68,116 KB |
testcase_25 | AC | 64 ms
68,116 KB |
testcase_26 | AC | 65 ms
68,116 KB |
testcase_27 | AC | 63 ms
68,116 KB |
testcase_28 | AC | 143 ms
86,776 KB |
testcase_29 | AC | 170 ms
94,172 KB |
testcase_30 | AC | 159 ms
91,240 KB |
testcase_31 | AC | 148 ms
88,480 KB |
testcase_32 | AC | 165 ms
92,184 KB |
testcase_33 | AC | 186 ms
96,504 KB |
testcase_34 | AC | 186 ms
96,424 KB |
testcase_35 | AC | 192 ms
96,668 KB |
testcase_36 | AC | 195 ms
96,640 KB |
ソースコード
# 可合并的线性基 from typing import List, Optional class VectorSpace: @staticmethod def merge(v1: "VectorSpace", v2: "VectorSpace") -> "VectorSpace": """合并两个线性基, 返回合并后的线性基(注意会修改原有的线性基).""" if len(v1) < len(v2): v1, v2 = v2, v1 for v in v2._data: v1.add(v) return v1 @staticmethod def intersection(v1: "VectorSpace", v2: "VectorSpace", maxDim: int) -> "VectorSpace": """求两个线性基的交集, 返回交集的线性基(注意会修改原有的线性基).""" x = v1._orthogonalSpace(maxDim) y = v2._orthogonalSpace(maxDim) x = VectorSpace.merge(x, y) return x._orthogonalSpace(maxDim) __slots__ = ("_data",) def __init__(self, nums: Optional[List[int]] = None) -> None: self._data = [] if nums is not None: for v in nums: self.add(v) def add(self, v: int) -> bool: for e in self._data: if e == 0 or v == 0: break v = min(v, v ^ e) if v: self._data.append(v) return True return False def getMax(self, xorVal=0) -> int: res = xorVal for e in self._data: res = max(res, res ^ e) return res def getMin(self, xorVal=0) -> int: res = xorVal for e in self._data: res = min(res, res ^ e) return res def _orthogonalSpace(self, maxDim: int) -> "VectorSpace": self._normalize() m = maxDim tmp = [0] * m for e in self._data: tmp[e.bit_length() - 1] = e tmp = transpose(m, m, tmp, inplace=True) res = VectorSpace() for j in range(m): if tmp[j] & (1 << j): continue res.add(tmp[j] | (1 << j)) return res def _normalize(self, reverse=True) -> None: n = len(self._data) for j in range(n): for i in range(j): self._data[i] = min(self._data[i], self._data[i] ^ self._data[j]) self._data.sort(reverse=reverse) def __len__(self) -> int: return len(self._data) def __contains__(self, v: int) -> bool: for e in self._data: if v == 0: break v = min(v, v ^ e) return v == 0 def transpose(row: int, col: int, matrix1D: List[int], inplace=False) -> List[int]: """矩阵转置 matrix1D:每个元素是状压的数字 inplace:是否修改原矩阵 """ assert row == len(matrix1D) m = matrix1D[:] if not inplace else matrix1D log = 0 max_ = max(row, col) while (1 << log) < max_: log += 1 if len(m) < (1 << log): m += [0] * ((1 << log) - len(m)) w = 1 << log mask = 1 for i in range(log): mask = mask | (mask << (1 << i)) for t in range(log): w >>= 1 mask = mask ^ (mask >> w) for i in range(1 << t): for j in range(w): m[w * 2 * i + j] = ((m[w * (2 * i + 1) + j] << w) & mask) ^ m[w * 2 * i + j] m[w * (2 * i + 1) + j] = ((m[w * 2 * i + j] & mask) >> w) ^ m[w * (2 * i + 1) + j] m[w * 2 * i + j] = ((m[w * (2 * i + 1) + j] << w) & mask) ^ m[w * 2 * i + j] return m[:col] if __name__ == "__main__": n = int(input()) nums = list(map(int, input().split())) print(2 ** len(VectorSpace(nums)))