結果
問題 | No.1937 Various Tournament |
ユーザー |
👑 |
提出日時 | 2022-05-13 22:10:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 798 ms / 2,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 244 ms |
コンパイル使用メモリ | 82,696 KB |
実行使用メモリ | 90,700 KB |
最終ジャッジ日時 | 2024-07-22 02:04:43 |
合計ジャッジ時間 | 26,854 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
def popcount(x): x = x - ((x >> 1) & 0x55555555) x = (x & 0x33333333) + ((x >> 2) & 0x33333333) x = (x + (x >> 4)) & 0x0f0f0f0f x += x >> 8 x += x >> 16 return x & 0x0000003f n = int(input()) S = [list(map(int, input().split())) for _ in range(n)] dp = [[0] * n for _ in range(1 << n)] for i in range(n): dp[1 << i][i] = 1 bits = [[] for _ in range(17)] se2 = {2, 4, 8, 16} for i in se2: for j in range(1 << i): if popcount(j) == i >> 1: bits[i >> 1].append(j) x = 0 for bit in range(3, 1 << n): cnt = 0 lst = [] for i in range(n): if bit >> i & 1: lst.append(i) cnt += 1 if cnt not in se2: continue half = cnt >> 1 x += len(bits[half]) for bbit in bits[half]: b1 = 0 b2 = 0 l1 = [] l2 = [] for i in range(cnt): if bbit >> i & 1: b1 |= 1 << lst[i] l1.append(lst[i]) else: b2 |= 1 << lst[i] l2.append(lst[i]) for i in l1: for j in l2: if S[i][j]: dp[bit][i] += dp[b1][i] * dp[b2][j] else: dp[bit][j] += dp[b2][j] * dp[b1][i] print(*dp[-1], sep="\n")