結果
問題 | No.2733 Just K-times TSP |
ユーザー | 沙耶花 |
提出日時 | 2024-04-19 21:58:41 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 867 bytes |
コンパイル時間 | 4,355 ms |
コンパイル使用メモリ | 267,168 KB |
実行使用メモリ | 17,876 KB |
最終ジャッジ日時 | 2024-10-11 15:04:26 |
合計ジャッジ時間 | 6,080 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 int main(){ int N,M,K; cin>>N>>M>>K; int t = 1; K++; rep(i,N)t *= K; vector<vector<int>> E(N); rep(i,M){ int u,v; cin>>u>>v; u--,v--; E[u].push_back(v); E[v].push_back(u); } vector dp(N,vector<mint>(t,0)); t = 1; rep(i,N){ dp[i][t] = 1; t *= K; } vector<int> x(N); x[0] = 1; rep(i,N-1)x[i+1] = x[i] * K; rep(j,t){ rep(i,N){ rep(k,E[i].size()){ int to = E[i][k]; int jj = j; jj /= x[to]; if(jj%K==K-1)continue; jj = j; jj += x[to]; dp[to][jj] +=dp[i][j]; } } } mint ans = 0; rep(i,N)ans += dp[i].back(); cout<<ans.val()<<endl; return 0; }