結果

問題 No.2733 Just K-times TSP
コンテスト
ユーザー norioc
提出日時 2025-10-21 20:52:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,316 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 110,452 KB
最終ジャッジ日時 2025-10-21 20:52:22
合計ジャッジ時間 9,860 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

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(start):
    size = pow(K+1, N)
    dp = [[0] * N for _ in range(size)]
    # dp[各都市の訪問回数][最後に訪れた都市]
    keys = [0] * N
    keys[start] = 1
    dp[pack(keys)][start] = 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 = sum(tsp(i) for i in range(N)) % MOD
print(ans)
0