結果

問題 No.2733 Just K-times TSP
コンテスト
ユーザー norioc
提出日時 2025-10-21 21:00:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,849 ms / 2,000 ms
コード長 1,331 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,740 KB
実行使用メモリ 142,288 KB
最終ジャッジ日時 2025-10-21 21:01:06
合計ジャッジ時間 10,299 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict

MOD = 998244353
N, M, K = map(int, input().split())
adj = defaultdict(list)
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    adj[u].append(v)
    adj[v].append(u)


def pack(keys: list[int]) -> int:
    # K+1 進数
    res = 0
    b = 1
    for k in keys:
        res += k * b
        b *= (K+1)

    # assert keys == unpack(res), (keys, unpack(res))
    return res


def unpack(x: int) -> list[int]:
    res = []
    s = x
    b = K+1
    for i in range(N):
        res.append(s % b)
        s //= b

    return res


def tsp():
    size = pow(K+1, N)
    dp = [[0] * N for _ in range(size)]
    # dp[各都市の訪問回数][最後に訪れた都市]
    for i in range(N):  # スタート都市
        keys = [0] * N
        keys[i] = 1
        dp[pack(keys)][i] = 1

    for i in range(size):
        cnts = unpack(i)
        for j in range(N):  # 最後に訪れた都市
            if cnts[j] == 0: continue
            for to in adj[j]:
                if cnts[to] == K: continue
                xs = cnts.copy()
                xs[to] += 1
                nk = pack(xs)
                dp[nk][to] += dp[i][j]
                dp[nk][to] %= MOD

    nk = pack([K] * N)
    res = sum(dp[nk][i] for i in range(N)) % MOD
    return res


ans = tsp()
print(ans)
0