結果
問題 | No.2733 Just K-times TSP |
ユーザー |
![]() |
提出日時 | 2024-09-21 19:03:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 657 ms / 2,000 ms |
コード長 | 2,197 bytes |
コンパイル時間 | 5,522 ms |
コンパイル使用メモリ | 259,504 KB |
実行使用メモリ | 32,224 KB |
最終ジャッジ日時 | 2024-09-21 19:03:59 |
合計ジャッジ時間 | 6,871 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using mint = atcoder::modint998244353;#define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++)#define ll long long//vector<T>であらわされるn進数を10進数に変換するtemplate<class T>T change_base_to_ten(const vector<T>& A, T n) {T ret = 0;T mul = 1;for (int i = (int)A.size()-1; i >= 0; i--) {ret += mul * A[i];mul *= n;}return ret;}//10進数でxのものをn進数に変換するtemplate<class T>vector<T> change_base_from_ten(T x, T n, int siz) {vector<T> ret;while(x != 0) {ret.push_back(x%n);x /= n;}while((int)ret.size() < siz) ret.push_back(0);reverse(ret.begin(), ret.end());return ret;}//n進法の桁のvectorであるSをm進法に変換するtemplate<class T>vector<T> change_base(const vector<T>& S, T n, T m) {T ten = change_base_to_ten(S, n);return change_base_from_ten(ten, m);}int pow(int x, int k) {int ret = 1;rep(_, 0, k) ret *= x;return ret;}int main() {int N, M, K; cin >> N >> M >> K;vector<vector<int>> G(N);rep(i, 0, M) {int u, v; cin >> u >> v;u--; v--;G[u].push_back(v);G[v].push_back(u);}vector<vector<mint>> dp(pow(K+1, N), vector<mint>(N));rep(i, 0, N) {vector<int> T(N, 0);T[i]++;// cout << change_base_to_ten(T, K+1) << endl;dp[change_base_to_ten(T, K+1)][i] = 1;}rep(S, 0, pow(K+1, N)) {// cout << "S = " << S << endl;vector<int> T = change_base_from_ten(S, K+1, N);// cout << "T = " << endl;// for (auto v : T) cout << v << " ";// cout << endl;rep(i, 0, N) {// cout << "i = " << i << endl;for (int to : G[i]) {// cout << "to = " << to << endl;if (T[to] >= K) continue;auto nT = T;nT[to]++;dp[change_base_to_ten(nT, K+1)][to] += dp[S][i];}}}mint ans = 0;rep(i, 0, N) ans += dp.back()[i];cout << ans.val() << endl;}