結果

問題 No.1937 Various Tournament
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:03:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,036 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 88,328 KB
最終ジャッジ日時 2025-06-12 15:05:07
合計ジャッジ時間 60,970 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    S = []
    for _ in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        S.append(row)
    
    participants = list(range(N))
    
    from collections import defaultdict
    memo = defaultdict(dict)
    
    def get_bitmask(subset):
        mask = 0
        for x in subset:
            mask |= 1 << x
        return mask
    
    def all_subsets():
        subsets = []
        for size in range(1, N+1):
            if (size & (size - 1)) != 0:
                continue
            for comb in combinations(participants, size):
                subsets.append( (size, comb) )
        return subsets
    
    all_subs = all_subsets()
    all_subs.sort(key=lambda x: x[0])
    
    for size, sub in all_subs:
        mask = get_bitmask(sub)
        if size == 1:
            k = sub[0]
            memo[mask][k] = 1
        else:
            half = size // 2
            total = 0
            for L in combinations(sub, half):
                R = tuple(x for x in sub if x not in L)
                mask_L = get_bitmask(L)
                mask_R = get_bitmask(R)
                for a in L:
                    if a not in memo[mask_L]:
                        continue
                    for b in R:
                        if b not in memo[mask_R]:
                            continue
                        ways_L = memo[mask_L][a]
                        ways_R = memo[mask_R][b]
                        product = ways_L * ways_R
                        for k in sub:
                            if a == k and S[k][b] == 1:
                                memo[mask][k] = memo[mask].get(k, 0) + product
                            if b == k and S[k][a] == 1:
                                memo[mask][k] = memo[mask].get(k, 0) + product
    full_mask = (1 << N) - 1
    for k in participants:
        print(memo[full_mask].get(k, 0))

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