結果

問題 No.2445 奇行列式
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:45:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,008 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 146,744 KB
最終ジャッジ日時 2025-03-31 17:46:03
合計ジャッジ時間 13,701 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from sys import stdin
    sys.setrecursionlimit(1 << 25)
    N, B = map(int, stdin.readline().split())
    MOD = 2 * B
    matrix = []
    for _ in range(N):
        row = list(map(int, stdin.readline().split()))
        matrix.append(row)
    
    # Compute permanent mod MOD using DP with bitmask
    max_mask = 1 << N
    dp = [0] * max_mask
    dp[0] = 1 % MOD
    # Precompute masks grouped by their bit count
    bits = [[] for _ in range(N+1)]
    for mask in range(max_mask):
        cnt = bin(mask).count('1')
        bits[cnt].append(mask)
    
    for k in range(N):
        row = matrix[k]
        for mask in bits[k]:
            val = dp[mask]
            if val == 0:
                continue
            for j in range(N):
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    dp[new_mask] = (dp[new_mask] + val * row[j]) % MOD
    permanent = dp[(1 << N) -1] % MOD
    
    # Compute determinant mod MOD using Gaussian elimination
    def det_mod(mat, mod):
        n = len(mat)
        mat = [row[:] for row in mat]
        det = 1 % mod
        for i in range(n):
            # Find the pivot with non-zero element
            pivot = -1
            for j in range(i, n):
                if mat[j][i] % mod != 0:
                    pivot = j
                    break
            if pivot == -1:
                return 0 % mod
            if pivot != i:
                mat[i], mat[pivot] = mat[pivot], mat[i]
                det = (-det) % mod
            # Multiply the inverse of the pivot element to the current row
            a = mat[i][i] % mod
            g, x, y = extended_gcd(a, mod)
            if g != 1:
                return 0 % mod
            inv = x % mod
            det = (det * a) % mod  # Multiply by the pivot before row operations
            # Scale the pivot row to make the leading coefficient 1
            for j in range(i, n):
                mat[i][j] = (mat[i][j] * inv) % mod
            # Eliminate other rows
            for k in range(n):
                if k == i:
                    continue
                factor = mat[k][i] % mod
                if factor == 0:
                    continue
                for j in range(i, n):
                    mat[k][j] = (mat[k][j] - factor * mat[i][j]) % mod
        # Calculate the product of the diagonal elements
        for i in range(n):
            det = (det * mat[i][i]) % mod
        return det
    
    def extended_gcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = extended_gcd(b % a, a)
            return (g, x - (b // a) * y, y)
    
    determinant = det_mod(matrix, MOD) % MOD
    
    # Compute (permanent - determinant) / 2 mod B
    diff = (permanent - determinant) % MOD
    # Ensure diff is even and non-negative
    if diff % 2 != 0:
        diff = (diff + MOD) % MOD
    ans = (diff // 2) % B
    print(ans)
    
if __name__ == '__main__':
    main()
0