結果

問題 No.2445 奇行列式
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:47:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,170 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 94,860 KB
最終ジャッジ日時 2025-03-20 20:48:06
合計ジャッジ時間 7,375 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_permanent_mod(A, N, mod):
    dp = [0] * (1 << N)
    dp[0] = 1
    for i in range(N):
        new_dp = [0] * (1 << N)
        for mask in range(1 << N):
            if bin(mask).count('1') != i:
                continue
            if dp[mask] == 0:
                continue
            temp = (~mask) & ((1 << N) - 1)
            while temp:
                lsb = temp & -temp
                j = (lsb.bit_length() - 1)
                new_mask = mask | lsb
                new_dp[new_mask] = (new_dp[new_mask] + dp[mask] * A[i][j]) % mod
                temp ^= lsb
        dp = new_dp
    return dp[(1 << N) - 1]

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)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None
    else:
        return x % m

def determinant_mod(matrix, m):
    matrix = [row[:] for row in matrix]
    n = len(matrix)
    result = 1
    for i in range(n):
        pivot = -1
        for j in range(i, n):
            if matrix[j][i] % m != 0:
                pivot = j
                break
        if pivot == -1:
            return 0
        if pivot != i:
            matrix[i], matrix[pivot] = matrix[pivot][:], matrix[i][:]
            result = (-result) % m
        inv = mod_inverse(matrix[i][i], m)
        if inv is None:
            return 0
        for j in range(i + 1, n):
            factor = (matrix[j][i] * inv) % m
            for k in range(i, n):
                matrix[j][k] = (matrix[j][k] - factor * matrix[i][k]) % m
        result = (result * matrix[i][i]) % m
    return result

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    B = int(input[idx])
    idx += 1
    mod = 2 * B
    A = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        idx += N
        A.append(row)
    perm = compute_permanent_mod(A, N, mod)
    det = determinant_mod(A, mod)
    s_minus_d = (perm - det) % mod
    ans = (s_minus_d // 2) % B
    print(ans)

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