結果

問題 No.2445 奇行列式
ユーザー lam6er
提出日時 2025-04-16 01:13:05
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,348 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 91,864 KB
最終ジャッジ日時 2025-04-16 01:14:36
合計ジャッジ時間 8,163 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 RE * 9 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    n, B = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    mod = 2 * B

    # Compute permanent using Ryser's algorithm with mod
    popcount = [bin(m).count('1') for m in range(1 << n)]
    permanent = 0
    for mask in range(1 << n):
        k = popcount[mask]
        sign = (-1) ** (n - k)
        product = 1
        for i in range(n):
            sum_i = 0
            temp = mask
            while temp:
                lsb = temp & -temp
                j = (lsb.bit_length() - 1)
                sum_i += A[i][j]
                temp ^= lsb
            sum_i %= mod
            product = (product * sum_i) % mod
        term = sign * product
        permanent = (permanent + term) % mod

    # Compute determinant using Gaussian elimination
    matrix = [row.copy() for row in A]
    det = 1
    for i in range(n):
        pivot = -1
        for j in range(i, n):
            if matrix[j][i] % mod != 0:
                pivot = j
                break
        if pivot == -1:
            det = 0
            break
        if pivot != i:
            matrix[i], matrix[pivot] = matrix[pivot], matrix[i]
            det = (-det) % mod
        for j in range(i + 1, n):
            while True:
                current = matrix[j][i] % mod
                if current == 0:
                    break
                # Use the row with the larger leading coefficient to reduce
                if matrix[i][i] % mod == 0:
                    matrix[i], matrix[j] = matrix[j], matrix[i]
                    det = (-det) % mod
                    continue
                factor = (current * pow(matrix[i][i], -1, mod)) % mod if matrix[i][i] != 0 else 0
                if factor == 0:
                    break
                for k in range(i, n):
                    matrix[j][k] = (matrix[j][k] - factor * matrix[i][k]) % mod
                # Check again after subtraction
                current = matrix[j][i] % mod
                if current != 0:
                    matrix[i], matrix[j] = matrix[j], matrix[i]
                    det = (-det) % mod
                else:
                    break
        det = (det * matrix[i][i]) % mod

    m = (permanent - det) % mod
    ans = (m // 2) % B
    print(ans)

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