結果

問題 No.803 Very Limited Xor Subset
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:09:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 82 ms / 2,000 ms
コード長 1,721 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 76,856 KB
最終ジャッジ日時 2025-03-20 21:10:21
合計ジャッジ時間 4,189 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    X = int(input[idx]); idx +=1
    
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    
    equations = []
    
    # XOR bit equations
    for k in range(30):
        mask = 0
        rhs = (X >> k) & 1
        for i in range(N):
            if (A[i] >> k) & 1:
                mask |= 1 << i
        equations.append( (mask, rhs) )
    
    # Constraints equations
    for _ in range(M):
        t = int(input[idx]); idx +=1
        l = int(input[idx]) -1; idx +=1
        r = int(input[idx]) -1; idx +=1
        mask = 0
        for i in range(l, r+1):
            mask |= 1 << i
        equations.append( (mask, t) )
    
    rank = 0
    n = N
    
    # Gaussian elimination in GF(2)
    for col in reversed(range(n)):
        pivot = -1
        for r in range(rank, len(equations)):
            if (equations[r][0] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            continue
        
        equations[rank], equations[pivot] = equations[pivot], equations[rank]
        current_mask, current_rhs = equations[rank]
        
        for r in range(len(equations)):
            if r != rank and ( (equations[r][0] >> col) & 1 ):
                equations[r] = ( equations[r][0] ^ current_mask, equations[r][1] ^ current_rhs )
        
        rank += 1
    
    # Check for inconsistency
    for r in range(rank, len(equations)):
        if equations[r][0] == 0 and equations[r][1] != 0:
            print(0)
            return
    
    print(pow(2, n - rank, MOD))

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