結果

問題 No.2445 奇行列式
ユーザー lam6er
提出日時 2025-03-20 20:56:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,884 bytes
コンパイル時間 401 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 87,672 KB
最終ジャッジ日時 2025-03-20 20:56:52
合計ジャッジ時間 6,915 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_permanent_mod(matrix, mod):
    n = len(matrix)
    dp = [0] * (1 << n)
    dp[0] = 1
    for row in range(n):
        for mask in range((1 << n) - 1, -1, -1):
            if bin(mask).count('1') != row:
                continue
            for col in range(n):
                if not (mask & (1 << col)):
                    new_mask = mask | (1 << col)
                    dp[new_mask] = (dp[new_mask] + dp[mask] * matrix[row][col]) % mod
    return dp[(1 << n) - 1]

def determinant_mod(matrix, mod):
    n = len(matrix)
    mat = [row[:] for row in matrix]
    for i in range(n):
        for j in range(n):
            mat[i][j] %= mod
    res = 1
    for i in range(n):
        pivot = -1
        for j in range(i, n):
            if mat[j][i] != 0:
                pivot = j
                break
        if pivot == -1:
            return 0
        if i != pivot:
            mat[i], mat[pivot] = mat[pivot], mat[i]
            res = (-res) % mod
        a = mat[i][i]
        for j in range(i + 1, n):
            b = mat[j][i]
            while b != 0:
                q, r = divmod(a, b)
                for k in range(i, n):
                    mat[i][k] = (mat[i][k] - q * mat[j][k]) % mod
                mat[i], mat[j] = mat[j], mat[i]
                res = (-res) % mod
                a, b = b, r
        if a == 0:
            return 0
        res = (res * a) % mod
    return res

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, B = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    matrix = []
    for _ in range(N):
        row = list(map(int, input[ptr:ptr+N]))
        ptr += N
        matrix.append(row)
    mod = 2 * B
    S = compute_permanent_mod(matrix, mod)
    D = determinant_mod(matrix, mod)
    delta = (S - D) % mod
    result = (delta // 2) % B
    print(result)

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