結果
問題 | No.2733 Just K-times TSP |
ユーザー |
|
提出日時 | 2024-04-20 13:05:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,231 ms / 2,000 ms |
コード長 | 1,022 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 82,072 KB |
実行使用メモリ | 116,568 KB |
最終ジャッジ日時 | 2024-10-12 08:29:57 |
合計ジャッジ時間 | 8,358 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
import syssys.setrecursionlimit(5*10**5)input = sys.stdin.readlinefrom collections import defaultdict, deque, Counterfrom heapq import heappop, heappushfrom bisect import bisect_left, bisect_rightfrom math import gcdn,m,k = map(int,input().split())graph = [[] for i in range(n+1)]for i in range(m):u,v = map(int,input().split())graph[u-1].append(v-1)graph[v-1].append(u-1)mod = 998244353mem = [-1]*(9**7)wa = 0for i in range(n):wa += k*pow(9, i)pows = [pow(9, i) for i in range(9)]def f(cnt):if cnt//9 == wa:mem[cnt] = 1return 1if mem[cnt] != -1:return mem[cnt]res = 0last = cnt % 9for nxt in graph[last]:now = (cnt//pows[nxt+1]) % 9if now == k: continuenew = cnt//9new += pows[nxt]new = new*9 + nxtres += f(new)res %= modmem[cnt] = resreturn resans = 0for i in range(n):cnt = 0cnt += pow(9, i+1)ans += f(cnt+i)ans %= modprint(ans)