結果

問題 No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
ユーザー lam6er
提出日時 2025-04-15 21:16:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,852 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 81,636 KB
実行使用メモリ 155,664 KB
最終ジャッジ日時 2025-04-15 21:22:26
合計ジャッジ時間 4,025 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations
from collections import defaultdict

def main():
    A = []
    for _ in range(19):
        parts = list(map(int, sys.stdin.readline().split()))
        L_i = parts[0]
        A_i = parts[1:] if L_i > 0 else []
        A.append(A_i)
    
    mask_gt = [0] * 20
    for x in range(1, 20):
        mask = ((1 << 19) - 1) ^ ((1 << x) - 1)
        mask_gt[x] = mask
    
    masks_by_bit_count = [[] for _ in range(20)]
    for k in range(20):
        for bits in combinations(range(19), k):
            mask = sum(1 << b for b in bits)
            masks_by_bit_count[k].append(mask)
    
    current_dp = [defaultdict(int), defaultdict(int)]
    current_dp[0][0] = 1
    
    for step in range(1, 20):
        current_bit_count = step - 1
        next_dp = [defaultdict(int) for _ in range(2)]
        allowed_x = A[step - 1]
        if not allowed_x:
            current_dp = next_dp
            continue
        
        for mask in masks_by_bit_count[current_bit_count]:
            for parity in [0, 1]:
                count = current_dp[parity].get(mask, 0)
                if count == 0:
                    continue
                for x in allowed_x:
                    if (mask & (1 << (x - 1))) != 0:
                        continue
                    gt_mask = mask_gt[x]
                    and_mask = mask & gt_mask
                    parity_contribution = bin(and_mask).count('1') % 2
                    new_parity = (parity + parity_contribution) % 2
                    new_mask = mask | (1 << (x - 1))
                    next_dp[new_parity][new_mask] += count
        
        current_dp = next_dp
    
    full_mask = (1 << 19) - 1
    X_even = current_dp[0].get(full_mask, 0)
    X_odd = current_dp[1].get(full_mask, 0)
    print(X_even, X_odd)

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