結果

問題 No.2445 奇行列式
コンテスト
ユーザー lam6er
提出日時 2025-04-16 01:05:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,597 ms / 3,000 ms
コード長 1,971 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 81,784 KB
実行使用メモリ 93,304 KB
最終ジャッジ日時 2025-04-16 01:07:26
合計ジャッジ時間 10,849 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    B = int(input[idx])
    idx += 1
    A = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        idx += N
        A.append(row)
    
    mod = 2 * B
    max_mask = 1 << N
    dp = [0] * max_mask
    dp[0] = 1
    bit_count = [0] * max_mask
    for mask in range(max_mask):
        bit_count[mask] = bin(mask).count('1')
    
    for k in range(N):
        for mask in range(max_mask):
            if bit_count[mask] != k:
                continue
            current = dp[mask]
            if current == 0:
                continue
            for j in range(N):
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    val = (current * A[k][j]) % mod
                    dp[new_mask] = (dp[new_mask] + val) % mod
    P = dp[(1 << N) - 1]
    
    def compute_determinant(mat):
        n = len(mat)
        det = 1
        mat = [row[:] for row in mat]
        for c in range(n):
            pivot_row = -1
            for r in range(c, n):
                if mat[r][c] != 0:
                    pivot_row = r
                    break
            if pivot_row == -1:
                return 0
            if pivot_row != c:
                mat[c], mat[pivot_row] = mat[pivot_row], mat[c]
                det *= -1
            for r in range(c + 1, n):
                while mat[r][c] != 0:
                    factor = mat[r][c] // mat[c][c]
                    for j in range(c, n):
                        mat[r][j] -= factor * mat[c][j]
                    if mat[r][c] != 0:
                        mat[c], mat[r] = mat[r], mat[c]
                        det *= -1
            det *= mat[c][c]
        return det
    
    D = compute_determinant(A)
    D_mod = D % mod
    diff = (P - D_mod) % mod
    O = (diff // 2) % B
    print(O)

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