結果

問題 No.2445 奇行列式
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:23:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,593 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 266,216 KB
最終ジャッジ日時 2025-04-24 12:25:24
合計ジャッジ時間 9,268 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    B = int(input[idx])
    idx += 1
    matrix = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+N]))
        idx += N
        matrix.append(row)
    
    M = 2 * B
    n = N
    A = []
    for row in matrix:
        new_row = [x % M for x in row]
        A.append(new_row)
    
    # Compute determinant
    size = 1 << n
    even = [0] * size
    odd = [0] * size
    if n == 0:
        det = 0
    else:
        # Initialize for row 0
        for j in range(n):
            mask = 1 << j
            even[mask] = A[0][j] % M
        # Process rows 1 to n-1
        for i in range(1, n):
            current_masks = []
            for cols in combinations(range(n), i):
                mask = 0
                for c in cols:
                    mask |= 1 << c
                current_masks.append(mask)
            new_even = [0] * size
            new_odd = [0] * size
            for mask in current_masks:
                ce = even[mask]
                co = odd[mask]
                if ce == 0 and co == 0:
                    continue
                # Iterate all j not in mask
                for j in range(n):
                    if not (mask & (1 << j)):
                        # Compute count of bits > j in mask
                        count = bin((mask >> (j + 1))).count('1')
                        new_mask = mask | (1 << j)
                        # Process even contribution
                        new_parity = (0 + count) % 2
                        contrib = (ce * A[i][j]) % M
                        if new_parity == 0:
                            new_even[new_mask] = (new_even[new_mask] + contrib) % M
                        else:
                            new_odd[new_mask] = (new_odd[new_mask] + contrib) % M
                        # Process odd contribution
                        new_parity = (1 + count) % 2
                        contrib = (co * A[i][j]) % M
                        if new_parity == 0:
                            new_even[new_mask] = (new_even[new_mask] + contrib) % M
                        else:
                            new_odd[new_mask] = (new_odd[new_mask] + contrib) % M
            even, odd = new_even, new_odd
        full_mask = (1 << n) - 1
        det = (even[full_mask] - odd[full_mask]) % M
    
    # Compute permanent
    perm_dp = [0] * size
    if n == 0:
        perm = 0
    else:
        # Initialize for row 0
        for j in range(n):
            mask = 1 << j
            perm_dp[mask] = A[0][j] % M
        # Process rows 1 to n-1
        for i in range(1, n):
            current_masks = []
            for cols in combinations(range(n), i):
                mask = 0
                for c in cols:
                    mask |= 1 << c
                current_masks.append(mask)
            new_dp = [0] * size
            for mask in current_masks:
                current = perm_dp[mask]
                if current == 0:
                    continue
                for j in range(n):
                    if not (mask & (1 << j)):
                        new_mask = mask | (1 << j)
                        new_dp[new_mask] = (new_dp[new_mask] + current * A[i][j]) % M
            perm_dp = new_dp
        full_mask = (1 << n) - 1
        perm = perm_dp[full_mask]
    
    s_odd = (perm - det) % M
    if s_odd < 0:
        s_odd += M
    s_odd = s_odd // 2
    answer = s_odd % B
    print(answer)

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