結果
問題 | No.2733 Just K-times TSP |
ユーザー |
|
提出日時 | 2024-04-19 22:19:45 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 190 ms / 2,000 ms |
コード長 | 1,798 bytes |
コンパイル時間 | 13,537 ms |
コンパイル使用メモリ | 379,512 KB |
実行使用メモリ | 47,488 KB |
最終ジャッジ日時 | 2024-10-11 15:46:24 |
合計ジャッジ時間 | 15,474 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]fn main() {let [N, M, K] = read_words::<usize>()[..] else { return };let edges = (0 .. M).map(|_| read_words::<usize>() ).collect::<Vec<_>>();let mut graph = vec![vec![]; N];for edge in &edges {let u = edge[0] - 1;let v = edge[1] - 1;graph[u].push(v);graph[v].push(u);}let mut pow = vec![1; N + 1];for i in 0 .. N {pow[i + 1] = pow[i] * (K + 1) % MOD;}let mut dp = vec![vec![0; N]; pow[N]];for i in 0 .. N {dp[pow[i]][i] = 1;}for state in 1 .. pow[N] {for last in 0 .. N {let c = dp[state][last];for &v in &graph[last] {let count = state / pow[v] % (K + 1);if count < K {let x = &mut dp[state + pow[v]][v];*x = add(*x, c);}}}}let mut sum = 0;for i in 0 .. N {sum += dp[pow[N] - 1][i];sum %= MOD;}println!("{}", sum);}fn add(x: usize, y: usize) -> usize {let mut z = x + y;if z >= MOD {z -= MOD;}z}type Int = usize;const MOD: Int = 998_244_353;const INF: Int = 1_000_000_000;const YESNO: [&'static str; 2] = ["Yes", "No"];use std::collections::*;use std::cmp::Reverse;fn read_line() -> String { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).ok(); buf }fn read_words<T: std::str::FromStr>() -> Vec<T> where T::Err: std::fmt::Debug { read_line().split_whitespace().map(|x| T::from_str(x).unwrap()).collect() }fn yes() { println!("{}", YESNO[0]); }fn no() { println!("{}", YESNO[1]); }fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }fn neighbor4<F: FnMut(usize, usize)>(i: usize, j: usize, h: usize, w: usize, mut f: F) { if i > 0 { (f)(i - 1, j); } if i < h - 1 { (f)(i + 1, j); }if j > 0 { (f)(i, j - 1); } if j < w - 1 { (f)(i, j + 1); } }