結果

問題 No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
ユーザー lam6er
提出日時 2025-04-16 15:25:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 367 ms / 1,000 ms
コード長 2,040 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 133,316 KB
最終ジャッジ日時 2025-04-16 15:26:01
合計ジャッジ時間 15,168 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

def read_input():
    M = [[0]*19 for _ in range(19)]
    for i in range(19):
        parts = list(map(int, sys.stdin.readline().split()))
        L_i = parts[0]
        elements = parts[1:]
        for x in elements:
            j = x - 1  # convert to 0-based
            M[i][j] = 1
    return M

def determinant_bareiss(matrix):
    n = len(matrix)
    m = [row[:] for row in matrix]
    sign = 1
    prev_pivot = 1
    for k in range(n-1):
        # Find pivot in column k
        pivot_row = -1
        for i in range(k, n):
            if m[i][k] != 0:
                pivot_row = i
                break
        if pivot_row == -1:
            return 0
        if pivot_row != k:
            m[k], m[pivot_row] = m[pivot_row], m[k]
            sign *= -1
        pivot = m[k][k]
        for i in range(k+1, n):
            for j in range(k+1, n):
                m[i][j] = (m[i][j] * pivot - m[i][k] * m[k][j]) // prev_pivot
            m[i][k] = 0
        prev_pivot = pivot
    det = sign * m[-1][-1]
    return det

def compute_permanent(M):
    n = 19
    dp = [0] * (1 << n)
    dp[0] = 1
    for i in range(n):
        next_dp = [0] * (1 << n)
        # Generate all masks with i bits set.
        for bits in combinations(range(n), i):
            mask = 0
            for b in bits:
                mask |= (1 << b)
            current_count = dp[mask]
            if current_count == 0:
                continue
            # Iterate over all possible j in this row.
            for j in range(n):
                if M[i][j] == 0:
                    continue
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    next_dp[new_mask] += current_count
        dp = next_dp
    return dp[(1 << n) - 1]

def main():
    M = read_input()
    det = determinant_bareiss(M)
    perm = compute_permanent(M)
    X_even = (perm + det) // 2
    X_odd = (perm - det) // 2
    print(X_even, X_odd)

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