結果

問題 No.1937 Various Tournament
ユーザー lam6er
提出日時 2025-04-09 21:04:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,835 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 112,544 KB
最終ジャッジ日時 2025-04-09 21:06:26
合計ジャッジ時間 3,900 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 1 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from functools import lru_cache
import math
from itertools import combinations

def main():
    N = int(stdin.readline())
    S = []
    for _ in range(N):
        row = list(map(int, stdin.readline().split()))
        S.append(row)
    
    full_mask = (1 << N) - 1
    memo = {}
    
    @lru_cache(maxsize=None)
    def dp(mask, k):
        m = bin(mask).count('1')
        if m == 1:
            return 1 if (mask & (1 << k)) else 0
        if (mask, k) in memo:
            return memo[(mask, k)]
        
        log_m = m.bit_length() - 1
        if (1 << log_m) != m:
            memo[(mask, k)] = 0
            return 0
        
        size = m
        split_size = size // 2
        ans = 0
        
        participants = [i for i in range(N) if (mask & (1 << i))]
        for left in combinations(participants, split_size):
            left_mask = 0
            for p in left:
                left_mask |= (1 << p)
            right_mask = mask ^ left_mask
            if right_mask == 0:
                continue
            
            if k in left:
                left_count = dp(left_mask, k)
                right_count = 0
                for w in participants:
                    if (right_mask & (1 << w)) and S[k][w]:
                        right_count += dp(right_mask, w)
                ans += left_count * right_count
            else:
                right_count = dp(right_mask, k)
                left_count = 0
                for w in participants:
                    if (left_mask & (1 << w)) and S[k][w]:
                        left_count += dp(left_mask, w)
                ans += left_count * right_count
        
        memo[(mask, k)] = ans
        return ans
    
    for k in range(N):
        print(dp(full_mask, k))

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