結果
問題 |
No.3229 Liar Game Comibination
|
ユーザー |
|
提出日時 | 2025-08-08 21:55:59 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,139 bytes |
コンパイル時間 | 729 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 101,980 KB |
最終ジャッジ日時 | 2025-08-08 21:56:16 |
合計ジャッジ時間 | 8,214 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 TLE * 1 -- * 9 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### from typing import Optional import typing class BitSet: """64 Bit""" def __init__(self, n: int): self.n = n self.buf = [0] * ((n + 63) // 64) def __getitem__(self, idx: int) -> int: return self.buf[idx >> 6] >> (idx & 0x3F) & 1 def __setitem__(self, idx: int, b: int) -> None: # assert b == 0 or b == 1 if b: self.buf[idx >> 6] |= 1 << (idx & 0x3F) else: self.buf[idx >> 6] &= ~(1 << (idx & 0x3F)) def __and__(self, other: "BitSet") -> "BitSet": return self.__xor__(other) def __or__(self, other: "BitSet") -> "BitSet": for i in range(len(self.buf)): self.buf[i] |= other.buf[i] return self def __xor__(self, other: "BitSet") -> "BitSet": for i in range(len(self.buf)): self.buf[i] ^= other.buf[i] return self def tostr(self) -> str: res = ["1" if self[i] else "0" for i in range(self.n)] return "".join(res) def copy(self) -> "BitSet": res = BitSet(self.n) res.buf = self.buf[:] return res class BitMatrix: def __init__(self, n: int, m: int): self.n = n self.m = m self.flip = False if n > m: self.flip = True n, m = m, n self.bss = [BitSet(m) for _ in range(n)] def __getitem__(self, idx: int) -> BitSet: return self.bss[idx] @staticmethod def from_input(n: int, m: int) -> "BitMatrix": res = BitMatrix(n, m) for i in range(n): row = input() # assert len(row) == m for j, c in enumerate(row): if c == "1": res.set(i, j, 1) return res @staticmethod def from_str(s: list[str]) -> "BitMatrix": n = len(s) m = len(s[0]) res = BitMatrix(n, m) for i in range(n): for j, c in enumerate(s[i]): if c == "1": res.set(i, j, 1) return res def copy(self) -> "BitMatrix": res = BitMatrix(0, 0) res.n, res.m, res.flip = self.n, self.m, self.flip res.bss = [bs.copy() for bs in self.bss] return res def tostr(self) -> str: res = [] for row in self.bss: res.append(row.tostr()) return "\n".join(res) def set(self, i: int, j: int, x: int) -> None: # assert x == 0 or x == 1 if self.flip: i, j = j, i # assert 0 <= i < self.n # assert 0 <= j < self.m self.bss[i][j] = x def get(self, i: int, j: int) -> int: if self.flip: i, j = j, i # assert 0 <= i < self.n # assert 0 <= j < self.m return self.bss[i][j] def rank(self): if self.n == 0 or self.m == 0: return 0 n, m = (self.m, self.n) if self.flip else (self.n, self.m) nonzero = [] lead = [] for i in range(n): ai = self.bss[i].copy() for aj, z in zip(nonzero, lead): if ai[z]: ai ^= aj bj = -1 for j in range(m): if ai[j]: bj = j break if bj >= 0: nonzero.append(ai.copy()) lead.append(bj) return len(nonzero) def det(self) -> int: assert self.n == self.m tmp = self.copy() for i in range(self.n): for k in range(i + 1, self.n): if tmp.get(k, i): tmp.bss[i], tmp.bss[k] = tmp.bss[k], tmp.bss[i] break if not tmp.get(i, i): return 0 for k in range(i + 1, self.n): if tmp.get(k, i): tmp.bss[k] ^= tmp.bss[i] return 1 def inv(self) -> Optional["BitMatrix"]: assert self.n == self.m tmp = BitMatrix(self.n, self.n << 1) tmp.flip = self.flip tmp.bss[: self.m] = self.bss[:] for i in range(self.n): tmp.set(i, i + self.n, 1) for i in range(self.n): for k in range(i + 1, self.n): if tmp.get(k, i): tmp.bss[i], tmp.bss[k] = tmp.bss[k], tmp.bss[i] if not tmp.get(i, i): return None for k in range(self.n): if k != i and tmp.get(k, i): tmp.bss[k] ^= tmp.bss[i] res = BitMatrix(self.n, self.n) for i in range(self.n): for j in range(self.n): if tmp.get(i, j + self.n): res.set(i, j, 1) return res n, m, k = na() A = BitMatrix.from_input(m, n) print(pow(2, n - A.rank(), k))