結果

問題 No.3024 全単射的
ユーザー lam6er
提出日時 2025-04-16 15:52:27
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,736 bytes
コンパイル時間 754 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 67,424 KB
最終ジャッジ日時 2025-04-16 15:53:29
合計ジャッジ時間 2,413 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd

def simplify(numerator, denominator):
    if denominator == 0:
        return None
    if denominator < 0:
        numerator = -numerator
        denominator = -denominator
    common = gcd(abs(numerator), denominator)
    return (numerator // common, denominator // common)

def add(a, b):
    num = a[0] * b[1] + b[0] * a[1]
    den = a[1] * b[1]
    return simplify(num, den)

def subtract(a, b):
    num = a[0] * b[1] - b[0] * a[1]
    den = a[1] * b[1]
    return simplify(num, den)

def multiply(a, b):
    num = a[0] * b[0]
    den = a[1] * b[1]
    return simplify(num, den)

def divide(a, b):
    if b[0] == 0:
        return None
    num = a[0] * b[1]
    den = a[1] * b[0]
    return simplify(num, den)

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    if n == 0:
        print("NO")
        return
    masks = [i for i in range(1, 1 << n)]
    masks.sort(key=lambda x: bin(x).count('1'))
    full_mask = (1 << n) - 1
    dp = {}

    for mask in masks:
        cnt = bin(mask).count('1')
        if cnt == 1:
            for i in range(n):
                if (mask >> i) & 1:
                    dp[mask] = {(a[i], 1)}
                    break
        else:
            dp[mask] = set()
            submask = (mask - 1) & mask
            while submask != 0:
                submask1 = submask
                submask2 = mask ^ submask1
                if submask1 in dp and submask2 in dp:
                    for x in dp[submask1]:
                        for y in dp[submask2]:
                            res = add(x, y)
                            if res is not None:
                                dp[mask].add(res)
                            res = subtract(x, y)
                            if res is not None:
                                dp[mask].add(res)
                            res = multiply(x, y)
                            if res is not None:
                                dp[mask].add(res)
                            if y[0] != 0:
                                res = divide(x, y)
                                if res is not None:
                                    dp[mask].add(res)
                submask = (submask - 1) & mask

    for mask in masks:
        if mask == 0 or mask == full_mask:
            continue
        complement = full_mask ^ mask
        if mask not in dp or complement not in dp:
            continue
        set1 = dp[mask]
        set2 = dp[complement]
        if len(set1) == 0 or len(set2) == 0:
            continue
        for x in set1:
            if x in set2:
                print("YES")
                return
    print("NO")

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