結果
問題 | No.1937 Various Tournament |
ユーザー |
![]() |
提出日時 | 2022-05-13 22:07:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 909 ms / 2,000 ms |
コード長 | 853 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 90,252 KB |
最終ジャッジ日時 | 2024-07-22 02:01:48 |
合計ジャッジ時間 | 28,702 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
import sys input = sys.stdin.readline def subset(N, k): S = (1<<k)-1 st = [] while S < (1<<N): st.append(S) x = S & -S y = S + x S = ((S & ~y) // x >> 1) | y return st N = int(input()) S = [list(map(int, input().split())) for _ in range(N)] dp = [[0] * N for _ in range(1<<N)] # dp[S][i] = number of ways where i wins the tournament of people in S for i in range(N): dp[1<<i][i] = 1 k = 0 while 2**k < N: st = subset(N, 2**k) for l, X in enumerate(st): for Y in st[l+1:]: if X&Y: continue for i in range(N): if X>>i&1: for j in range(N): if Y>>j&1: dp[X|Y][i if S[i][j] else j] += dp[X][i] * dp[Y][j] * 2 k += 1 for i in range(N): print(dp[-1][i])