結果
問題 |
No.2152 [Cherry Anniversary 2] 19 Petals of Cherry
|
ユーザー |
👑 ![]() |
提出日時 | 2022-11-27 17:20:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 380 ms / 1,000 ms |
コード長 | 917 bytes |
コンパイル時間 | 222 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 88,960 KB |
最終ジャッジ日時 | 2024-10-14 18:04:33 |
合計ジャッジ時間 | 19,176 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 |
ソースコード
def solve(): N=19 B=[[0]*N for _ in range(N)] for i in range(N): _,*Ai=map(int,input().split()) for a in Ai: B[i][a-1]=1 popcount=[0]*(1<<N) for S in range(1,1<<N): popcount[S]=popcount[S>>1]+(S&1) bit=lambda S,k:(S>>k)&1 DP0=[0]*(1<<N); DP1=[0]*(1<<N) for S in range((1<<N)-1, -1, -1): if popcount[S]==N: DP0[S]=1 continue unused=[i for i in range(N) if not bit(S,i)] for t in range(len(unused)): if B[popcount[S]][unused[t]]==1: T=S|(1<<unused[t]) if t%2: DP0[S]+=DP1[T] DP1[S]+=DP0[T] else: DP0[S]+=DP0[T] DP1[S]+=DP1[T] return DP0[0], DP1[0] #================================================== print(*solve())