結果

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

ソースコード

diff # 

from collections import defaultdict


class BaseN:
    def __init__(self, b: int):
        self.b = b
        self.bs = [pow(b, i) for i in range(2)]

    def _expand(self, k):
        while k >= len(self.bs):
            self.bs.append(self.bs[-1] * self.b)

    def nth(self, x: int, k: int) -> int:
        """x の k 番目の桁の数字を取得 (1 の位が k=0)"""
        self._expand(k)
        r = x // self.bs[k]
        return r % self.b

    def at(self, k: int) -> int:
        """b^k を返す (1 の位が k=0)"""
        self._expand(k)
        return self.bs[k]


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 tsp():
    b = BaseN(K+1)
    size = b.at(N)
    dp = [[0] * N for _ in range(size)]
    # dp[各都市の訪問回数][最後に訪れた都市]
    for i in range(N):  # スタート都市
        dp[b.at(i)][i] = 1

    for i in range(size):
        for j in range(N):  # 最後に訪れた都市
            if b.nth(i, j) == 0: continue

            for to in adj[j]:
                if b.nth(i, to) == K: continue  # 上限

                nk = i + b.at(to)
                dp[nk][to] += dp[i][j]
                dp[nk][to] %= MOD

    nk = size-1
    res = sum(dp[nk][i] for i in range(N)) % MOD
    return res


ans = tsp()
print(ans)
0