結果

問題 No.3229 Liar Game Comibination
コンテスト
ユーザー wasd314
提出日時 2025-08-08 22:38:30
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,074 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 279,376 KB
最終ジャッジ日時 2025-08-08 22:38:42
合計ジャッジ時間 10,717 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 RE * 4 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 2

def inplace_sweep(n: int, m: int, a):
    # returns [is pivot]
    piv = [False] * m
    r = 0
    for j in range(m):
        if a[r][j] == 0:
            for i in range(r + 1, n):
                if a[i][j]:
                    a[r], a[i] = a[i], a[r]
                    break
        if a[r][j] == 0:
            continue
        inv = pow(a[r][j], -1, mod)
        a[r] = [e * inv % mod for e in a[r]]
        ar = a[r]
        for i in range(n):
            c = a[i][j]
            if i == r or c == 0:
                continue
            a[i] = [(e - c * er) % mod for e, er in zip(a[i], ar)]
        piv[j] = True
        r += 1
        if r == n:
            break
    return piv

def solve_linear_equation(n: int, m: int, a, b):
    """returns (x0, rank, ker basis) | None"""
    if n == 0:
        es = [[0] * m for _ in range(m)]
        for i in range(m):
            es[i][i] = 1
        return [], m, es
    exa = [[e % mod for e in ai] + [bi % mod] for ai, bi in zip(a, b)]
    is_piv = inplace_sweep(n, m + 1, exa)
    r = sum(is_piv)
    if r == 0:
        es = [[0] * m for _ in range(m)]
        for i in range(m):
            es[i][i] = 1
        return [0] * m, m, es
    if is_piv[m]:
        return None

    piv = [i for i in range(m) if is_piv[i]]
    un_piv = [i for i in range(m) if not is_piv[i]]

    x0 = [0] * m
    for i, p in enumerate(piv):
        x0[p] = exa[i][m]
    es = [[0] * m for _ in range(m - r)]
    for i, p in enumerate(piv):
        row = exa[i]
        for j, up in enumerate(un_piv):
            es[j][p] = mod - row[up] if row[up] else 0
    for i, p in enumerate(un_piv):
        es[i][p] = 1
    return x0, m - r, es

def main():
    from sys import stdin

    def input():
        return stdin.readline().rstrip("\n")

    n, m, k = map(int, input().split())
    a = [tuple(map(int, input())) for _ in range(n)]
    b = [0] * m
    ans = solve_linear_equation(m, n, a, b)
    if ans is None:
        print(0)
        return
    x0, r, es = ans
    print(pow(2, r, k))

if __name__ == "__main__":
    main()
0