結果

問題 No.2733 Just K-times TSP
ユーザー prd_xxx
提出日時 2024-04-19 22:36:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 449 ms / 2,000 ms
コード長 737 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 100,956 KB
最終ジャッジ日時 2024-10-11 16:15:30
合計ジャッジ時間 4,632 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M,K = map(int,input().split())
UV= [tuple(map(int,input().split())) for _ in range(M)]
if N==1:
    exit(print(1 if K==1 else 0))
MOD = 998244353

es = [[] for _ in range(N)]
for u,v in UV:
    u,v = u-1,v-1
    es[u].append(v)
    es[v].append(u)

L = (K+1)**N
dp = [[0]*L for _ in range(N)]
for i in range(N):
    dp[i][(K+1)**i] = 1

for v in range(L):
    cnt = []
    _v = v
    for _ in range(N):
        _v,m = divmod(_v,K+1)
        cnt.append(m)
    for i in range(N):
        if dp[i][v] == 0: continue
        for j in es[i]:
            if cnt[j]==K: continue
            nv = v + (K+1)**j
            dp[j][nv] += dp[i][v]
            dp[j][nv] %= MOD

ans = 0
for i in range(N):
    ans += dp[i][-1]
ans %= MOD
print(ans)
0