結果

問題 No.2733 Just K-times TSP
ユーザー titia
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
from itertools import product
mod=998244353
N,M,K=map(int,input().split())
E=[[] for i in range(N)]
def enc(x):
now=1
ANS=0
for i in range(len(x)-1):
ANS+=now*x[i]
now*=K+1
ANS+=now*x[-1]
return ANS
def dec(x):
X=[]
for i in range(N):
X.append(x%(K+1))
x//=K+1
X.append(x)
return X
for i in range(M):
u,v=map(int,input().split())
u-=1
v-=1
E[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]+=1
DP[enc(x)]=1
P=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]=i
if i==0:
pp=enc(X)
moto=pp
k=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)%mod
ANS=0
for i in range(N):
x=[K]*N+[i]
ANS+=DP[enc(x)]
return ANS%mod
print(calc(N,M,K,E))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0