結果

問題 No.2251 Marking Grid
コンテスト
ユーザー a
提出日時 2024-12-07 19:35:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,412 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 235,300 KB
最終ジャッジ日時 2024-12-07 19:35:46
合計ジャッジ時間 20,340 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

MOD = 998244353

# XOR Union-Find
class XORUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
        # dist[i]: iとparent[i]を繋ぐエッジのXOR値
        self.dist = [0]*n

    def find(self, x):
        if self.parent[x] == x:
            return x
        px = self.parent[x]
        self.parent[x] = self.find(px)
        self.dist[x] ^= self.dist[px]  # 経路圧縮時にdistも更新
        return self.parent[x]

    def union(self, x, y, w):
        # w = dist[x]^dist[y]になるようにx,yを統合
        # 既に同じ集合にある場合は一貫性チェック
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            # 矛盾チェック
            if (self.dist[x]^self.dist[y]) != w:
                return False, 0
            return True, 0
        # unite
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
            x, y = y, x
        self.parent[ry] = rx
        self.dist[ry] = self.dist[x]^self.dist[y]^w
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True, 1  # 新たな独立制約分、次元が1減る

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def xor_dist(self, x, y):
        # 同じ集合内でdist[x]^dist[y]を求める
        if self.find(x) != self.find(y):
            return None
        return self.dist[x]^self.dist[y]

# 累積用2べきテーブル
def precompute_powers_of_two(n, mod):
    res = [1]*(n+1)
    for i in range(1, n+1):
        res[i] = (res[i-1]*2) % mod
    return res

def solve():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]

    cells = []
    for i in range(H):
        for j in range(W):
            cells.append((A[i][j], i, j))

    # ソート
    cells.sort(key=lambda x:x[0])

    # XOR Union-Find 準備
    # R[i]:0<=i<H, C[j]:H<=H+j<H+W
    n = H+W
    xuf = XORUnionFind(n)

    # 初期自由度
    # 良い印の付け方の総空間は2^(H+W-1)
    dimension = H+W-1

    pow2 = precompute_powers_of_two(H*W+10, MOD)

    result = 0
    prev_count = 0 # #subsets(max < v) を記録（2^(d)-1の形）

    # 同じ値ごとにまとめる
    from itertools import groupby
    for val, group in groupby(cells, key=lambda x:x[0]):
        # 同じ値のセルについて R[i] XOR C[j] = 0 を追加
        # これにより「これ以上大きい値を使わない」制約を課していくことになる
        for _, r, c in group:
            # R[r], C[c]を同一視
            # xuf.union(r, H+c, 0)  => val=0
            ok, dec = xuf.union(r, H+c, 0)
            if not ok:
                # 矛盾が生じたら答え0 (問題設定上ないかもしれない)
                print(0)
                return
            dimension -= dec  # 独立制約増えたら次元減る

        # これで「最大値 ≤ val」な良い印付け方の数は2^(dimension)-1（空集合除く）
        current_count = (pow2[dimension]-1) % MOD
        diff = (current_count - prev_count) % MOD
        # diff は「最大値 = val」の印付け方の数
        # これに val を掛けて加算
        result = (result + val * diff) % MOD
        prev_count = current_count

    print(result % MOD)


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