Day 023-Q2 | 行列式計算 (Bareiss / mod)

問題

$N \times N$ の整数行列 $A$ が与えられる。$\det(A) \bmod (10^9 + 7)$ を求めよ。浮動小数点演算は精度不足で使えないため、整数演算（mod 演算）のみで行列式を計算する。

入力形式

N
A[0][0] A[0][1] ... A[0][N-1]
...
A[N-1][0] ... A[N-1][N-1]

制約

$1 \le N \le 500$

$-10^9 \le A[i][j] \le 10^9$

入出力例

入力例 1

出力例 1

999999996

$\det = -3 \equiv 10^9 + 7 - 3 = 999999996 \pmod{10^9+7}$

ヒント (段階的開示)

ヒント1: 方向性

mod 素数なら $\mathbb{Z}/p\mathbb{Z}$ は体なので、フェルマーの小定理による逆元 $a^{p-2}$ を使ってガウス消去が可能。

ヒント2: アプローチ

列ごとに非ゼロピボットを探し、行スワップ毎に符号を反転、ピボット以下の行を逆元で消去。対角成分の積が行列式。

ヒント3: 誘導

inv = pow(A[col][col], MOD-2, MOD)
for row in range(col+1, n):
    factor = A[row][col] * inv % MOD
    for j in range(col, n):
        A[row][j] = (A[row][j] - factor * A[col][j]) % MOD

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    MOD = 10**9 + 7
    N = int(input())
    A = []
    for _ in range(N):
        row = list(map(int, input().split()))
        A.append([x % MOD for x in row])

    def det_mod(A, mod):
        n = len(A)
        A = [row[:] for row in A]
        sign = 1
        for col in range(n):
            pivot_row = -1
            for row in range(col, n):
                if A[row][col] != 0:
                    pivot_row = row
                    break
            if pivot_row == -1:
                return 0
            if pivot_row != col:
                A[col], A[pivot_row] = A[pivot_row], A[col]
                sign = -sign
            inv_pivot = pow(A[col][col], mod - 2, mod)
            for row in range(col + 1, n):
                if A[row][col] == 0:
                    continue
                factor = A[row][col] * inv_pivot % mod
                for j in range(col, n):
                    A[row][j] = (A[row][j] - factor * A[col][j]) % mod
        result = sign
        for i in range(n):
            result = result * A[i][i] % mod
        return result % mod

    print(det_mod(A, MOD))

solve()

Step-by-Step 解説

1行列式の基本性質
行スワップで符号反転、行の線形結合は不変、上三角行列の行列式 = 対角成分の積。

2mod 素数でのガウス消去
$\mathbb{Z}/p\mathbb{Z}$ は体なので通常のガウス消去が使える。逆元は $a^{p-2} \bmod p$。計算量 $O(N^3)$。

3ピボット選択
浮動小数では数値的安定性のため最大値選択が重要だが、mod 演算では非ゼロを探せばよい。

4符号管理
行スワップ毎に sign = -sign。最終的に sign * diag_product % MOD。

よくあるミス

ミス	原因	正しい書き方
`pow(pivot, p-2, p)` でゼロ除算	ピボットが0	ピボット探索でゼロをスキップ
符号管理ミス	行スワップ回数の数え方	`sign = -sign` を毎回
結果が負	`% MOD` 忘れ	`result % MOD` で非負に
入力が負数	mod 変換前処理漏れ	入力時に `x % MOD`

Day 023-Q2 — 行列式計算 (Bareiss Algorithm + mod)

問題