結果
問題 | No.2733 Just K-times TSP |
ユーザー | eve__fuyuki |
提出日時 | 2024-04-19 22:01:09 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 1,554 bytes |
コンパイル時間 | 2,366 ms |
コンパイル使用メモリ | 213,404 KB |
実行使用メモリ | 32,256 KB |
最終ジャッジ日時 | 2024-10-11 15:08:31 |
合計ジャッジ時間 | 4,421 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using mint = atcoder::modint998244353; void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } vector<int> decode(int mask, int n, int k) { vector<int> res(n); for (int i = 0; i < n; i++) { res[i] = mask % k; mask /= k; } reverse(res.begin(), res.end()); return res; } int encode(const vector<int>& a, int n, int k) { int res = 0; for (int i = 0; i < a.size(); i++) { res = res * k + a[i]; } return res; } int main() { fast_io(); int n, m, k; cin >> n >> m >> k; vector<vector<int>> g(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } int tot = 1; for (int i = 0; i < n; i++) { tot *= k + 1; } vector<vector<mint>> dp(tot, vector<mint>(n)); for (int i = 0; i < n; i++) { vector<int> tmp(n); tmp[i] = 1; dp[encode(tmp, n, k + 1)][i] = 1; } for (int msk = 0; msk < tot; msk++) { vector<int> a = decode(msk, n, k + 1); for (int i = 0; i < n; i++) { for (int j : g[i]) { if (a[j] < k) { a[j]++; dp[encode(a, n, k + 1)][j] += dp[msk][i]; a[j]--; } } } } mint ans = 0; for (int i = 0; i < n; i++) { ans += dp[tot - 1][i]; } cout << ans.val() << endl; }