結果

問題 No.1421 国勢調査 (Hard)
コンテスト
ユーザー 草苺奶昔
提出日時 2023-03-20 14:18:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 2,534 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 79,564 KB
最終ジャッジ日時 2024-09-18 14:04:49
合計ジャッジ時間 4,842 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List, Optional


def solve_linear_equation_F2_col(A: List[int], b: List[int], m: int) -> Optional[List[int]]:
    """使用高斯消元法求解线性方程组Ax = b

    矩阵A 的每一行由一个整数表示,整数的二进制表示即为矩阵行的元素.
    向量b也是一个整数列表,每个元素对应一个二进制位.
    """
    assert len(A) == len(b)

    row = len(A)
    for r in range(row):
        indexes = max(range(r, row), key=lambda x: A[x])
        if A[indexes] == 0:
            rank = r
            break
        if indexes != r:
            A[r], A[indexes] = A[indexes], A[r]
            b[r], b[indexes] = b[indexes], b[r]
        for j in range(row):
            if r != j and A[j] > A[j] ^ A[r]:
                A[j] ^= A[r]
                b[j] ^= b[r]
    else:
        rank = row

    # 向量b在rank位置之后的所有元素是否为0。如果不是，返回None，表示方程无解。
    if any(b[i] for i in range(rank, row)):
        return

    res = [0] * m
    for r in range(rank):
        res[A[r].bit_length() - 1] = b[r]
    return res


if __name__ == "__main__":

    # https://yukicoder.me/problems/no/1421
    # 在一个国家里有n个城镇，它们分别被编号为1到n。在编号为i（1≤i≤n）的城镇中有ai栋房子，
    # 现在只知道这个情况。这个国家的国王想知道每个城镇分别有多少栋房子。
    # 有一天，m 个旅行者访问了这个国家。第j（1≤j≤m）个旅行者游览了国王的p个城镇，
    # 这些城镇的编号为Sj。每个旅行者j在离开国王时报告了以下两点：
    # !他们参观过的城市数量p，以及这些城市的编号Sj。
    # !他们参观过的p个城市中，房子数量的总XOR值。
    # !于是，国王决定根据m个旅行者的报告计算出每个城市的房子数量ai。
    # 但是，旅行者中可能有人提交了虚假的报告。
    # 如果存在一个与m个旅行者的所有报告相符的ai值组合，请输出其中的一个。
    # 如果没有（旅行者的报告中存在矛盾），请输出-1。

    n, m = map(int, input().split())
    A = [0] * m
    b = [0] * m
    for i in range(m):
        _ = int(input())
        houses = list(map(int, input().split()))
        xor_ = int(input())
        for house in houses:
            A[i] |= 1 << (house - 1)
        b[i] = xor_
    res = solve_linear_equation_F2_col(A, b, n)
    if res is None:
        print(-1)
    else:
        print(*res, sep="\n")
0