結果
問題 | No.2733 Just K-times TSP |
ユーザー |
![]() |
提出日時 | 2024-04-19 22:27:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 796 bytes |
コンパイル時間 | 5,083 ms |
コンパイル使用メモリ | 253,820 KB |
最終ジャッジ日時 | 2025-02-21 04:38:09 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using mint=modint998244353;int main(){int n,m,k;cin>>n>>m>>k;vector<int> u(m),v(m);vector<vector<int>> eg(n);for(int i=0;i<m;i++){cin>>u[i]>>v[i];u[i]--;v[i]--;eg[u[i]].push_back(v[i]);eg[v[i]].push_back(u[i]);}vector<int> pw(n+1);pw[0]=1;for(int i=0;i<n;i++)pw[i+1]=pw[i]*(k+1);vector<mint> dp(pw[n]*n);for(int i=0;i<n;i++)dp[pw[i]*n+i]=1;for(int i=0;i<pw[n]*n;i++){int pos=i%n;for(int j:eg[pos]){if(i/n/pw[j]%(k+1)==k)continue;dp[i+pw[j]*n-pos+j]+=dp[i];}}mint ans=0;for(int i=0;i<n;i++)ans+=dp[(pw[n]-1)*n+i];cout<<ans.val()<<"\n";}