結果
問題 | No.2733 Just K-times TSP |
ユーザー |
![]() |
提出日時 | 2024-04-20 02:08:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,609 ms / 2,000 ms |
コード長 | 1,401 bytes |
コンパイル時間 | 378 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 177,220 KB |
最終ジャッジ日時 | 2024-10-11 20:59:42 |
合計ジャッジ時間 | 9,239 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
import sysinput = sys.stdin.readlinefrom itertools import productmod=998244353N,M,K=map(int,input().split())E=[[] for i in range(N)]def enc(x):now=1ANS=0for i in range(len(x)-1):ANS+=now*x[i]now*=K+1ANS+=now*x[-1]return ANSdef dec(x):X=[]for i in range(N):X.append(x%(K+1))x//=K+1X.append(x)return Xfor i in range(M):u,v=map(int,input().split())u-=1v-=1E[u].append(v)E[v].append(u)def calc(N,M,K,E):DP=[0]*(((K+1)**N)*N)for i in range(N):x=[0]*N+[i]x[i]+=1DP[enc(x)]=1P=list(product(range(0,K+1),repeat=N))P.sort(key=lambda x:sum(x))POWK=[1]for i in range(N):POWK.append(POWK[-1]*(K+1)%mod)for Y in P:X=list(Y)+[0]for i in range(N):X[-1]=iif i==0:pp=enc(X)moto=ppk=DP[pp]else:pp+=POWK[-1]k=DP[pp]if k==0:continue#print(X)for to in E[i]:if X[to]+1<=K:qq=moto+to*POWK[-1]+POWK[to]DP[qq]=(DP[qq]+k)%modANS=0for i in range(N):x=[K]*N+[i]ANS+=DP[enc(x)]return ANS%modprint(calc(N,M,K,E))