結果

問題 No.1937 Various Tournament
ユーザー 👑 KazunKazun
提出日時 2022-05-13 22:49:52
言語 PyPy3
(7.3.8)
結果
AC  
実行時間 764 ms / 2,000 ms
コード長 888 bytes
コンパイル時間 253 ms
使用メモリ 96,384 KB
最終ジャッジ日時 2023-02-21 16:13:14
合計ジャッジ時間 26,252 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 76 ms
75,836 KB
testcase_01 AC 695 ms
96,316 KB
testcase_02 AC 712 ms
96,044 KB
testcase_03 AC 716 ms
95,952 KB
testcase_04 AC 716 ms
96,212 KB
testcase_05 AC 89 ms
80,780 KB
testcase_06 AC 727 ms
95,936 KB
testcase_07 AC 712 ms
96,348 KB
testcase_08 AC 89 ms
80,828 KB
testcase_09 AC 718 ms
96,060 KB
testcase_10 AC 89 ms
80,712 KB
testcase_11 AC 764 ms
96,288 KB
testcase_12 AC 720 ms
96,376 KB
testcase_13 AC 746 ms
96,020 KB
testcase_14 AC 717 ms
96,192 KB
testcase_15 AC 723 ms
96,252 KB
testcase_16 AC 718 ms
96,320 KB
testcase_17 AC 721 ms
95,940 KB
testcase_18 AC 740 ms
96,232 KB
testcase_19 AC 725 ms
96,224 KB
testcase_20 AC 91 ms
80,812 KB
testcase_21 AC 76 ms
75,920 KB
testcase_22 AC 736 ms
95,928 KB
testcase_23 AC 720 ms
96,296 KB
testcase_24 AC 722 ms
95,920 KB
testcase_25 AC 91 ms
80,748 KB
testcase_26 AC 723 ms
96,284 KB
testcase_27 AC 75 ms
75,864 KB
testcase_28 AC 714 ms
96,032 KB
testcase_29 AC 90 ms
80,648 KB
testcase_30 AC 732 ms
95,992 KB
testcase_31 AC 727 ms
96,220 KB
testcase_32 AC 723 ms
96,384 KB
testcase_33 AC 724 ms
96,236 KB
testcase_34 AC 732 ms
96,376 KB
testcase_35 AC 728 ms
95,952 KB
testcase_36 AC 720 ms
96,060 KB
testcase_37 AC 88 ms
80,724 KB
testcase_38 AC 90 ms
80,740 KB
testcase_39 AC 714 ms
96,332 KB
testcase_40 AC 89 ms
81,016 KB
testcase_41 AC 89 ms
81,140 KB
testcase_42 AC 733 ms
96,360 KB
testcase_43 AC 90 ms
80,772 KB
testcase_44 AC 76 ms
75,624 KB
testcase_45 AC 746 ms
96,280 KB
testcase_46 AC 90 ms
80,692 KB
testcase_47 AC 77 ms
75,664 KB
testcase_48 AC 76 ms
75,800 KB
testcase_49 AC 90 ms
80,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import combinations

N=int(input())

S=[]
for _ in range(N):
    S.append(list(map(int,input().split())))

DP=[[0]*N for _ in range(1<<N)]
for i in range(N):
    DP[1<<i][i]=1

popcount=[0]*(1<<N)
for A in range(1,1<<N):
    a=A&(-A)
    popcount[A]=popcount[A^a]+1

E=[A for A in range(1,1<<N) if (popcount[A]==1 or popcount[A]==2 or popcount[A]==4 or popcount[A]==8) and popcount[A]<N]
E.sort(key=lambda A:popcount[A])

for A in E:
    X=[]; Y=[]
    for a in range(N):
        if (A>>a)&1:
            X.append(a)
        else:
            Y.append(a)

    for B in combinations(Y,popcount[A]):
        T=0
        for b in B:
            T|=1<<b

        for a in X:
            for b in B:
                if S[a][b]==1:
                    DP[A|T][a]+=DP[A][a]*DP[T][b]
                else:
                    DP[A|T][b]+=DP[A][a]*DP[T][b]

print(*DP[-1],sep="\n")
0