結果
問題 | No.2733 Just K-times TSP |
ユーザー |
|
提出日時 | 2024-04-19 22:59:27 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,477 ms / 2,000 ms |
コード長 | 7,365 bytes |
コンパイル時間 | 15,002 ms |
コンパイル使用メモリ | 376,440 KB |
実行使用メモリ | 47,616 KB |
最終ジャッジ日時 | 2024-10-11 17:03:30 |
合計ジャッジ時間 | 22,214 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
#![allow(unused_imports)]//use itertools::{iproduct, Itertools};use proconio::input;use proconio::marker::*;use std::collections::*;fn main() {input! {n:usize,m:usize,k:usize,uv:[(Usize1,Usize1);m],}let mut g = vec![vec![]; n];for &(u, v) in uv.iter() {g[u].push(v);g[v].push(u);}let mut l = 0;for _ in 0..n {l = l * (k + 1) + k;}let mut dp = vec![vec![ModInt::<MOD>::new(0); n]; l + 1];for i in 0..n {dp[(k + 1).pow((n - i) as u32 - 1)][i] = ModInt::new(1);}for i in 0..l {let crr_cnts = base_n(i, k + 1, n);for crr in 0..n {for &nxt in g[crr].iter() {if crr_cnts[nxt] >= k {continue;}let mut nxt_cnts = 0;let mut tmp = vec![];for j in 0..n {nxt_cnts = if j == nxt {tmp.push(crr_cnts[j] + 1);nxt_cnts * (k + 1) + crr_cnts[j] + 1} else {tmp.push(crr_cnts[j]);nxt_cnts * (k + 1) + crr_cnts[j]};}dp[nxt_cnts][nxt] = dp[nxt_cnts][nxt] + dp[i][crr];}}}let mut ans = ModInt::new(0);for i in 0..n {ans += dp[l][i];}println!("{}", ans);}const MOD: usize = 998244353;use modint::*;mod modint {use std::fmt;use std::ops;#[derive(Copy, Clone, PartialEq, Eq)]pub struct ModInt<const MOD: usize> {pub val: usize,}impl<const MOD: usize> ModInt<MOD> {pub fn new(val: usize) -> Self {Self { val: val % MOD }}pub fn pow(mut self, mut e: usize) -> Self {let mut res = Self::new(1);while 0 < e {if e & 1 != 0 {res *= self;}self *= self;e >>= 1;}res}}impl<const MOD: usize> From<usize> for ModInt<MOD> {fn from(value: usize) -> Self {Self { val: value % MOD }}}impl<const MOD: usize> fmt::Display for ModInt<MOD> {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {write!(f, "{}", self.val)}}impl<const MOD: usize> fmt::Debug for ModInt<MOD> {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {write!(f, "{}", self.val)}}impl<const MOD: usize> ops::Neg for ModInt<MOD> {type Output = Self;fn neg(self) -> Self::Output {Self {val: (MOD - self.val) % MOD,}}}impl<const MOD: usize> ops::Add for ModInt<MOD> {type Output = Self;fn add(self, rhs: Self) -> Self::Output {Self {val: (self.val + rhs.val) % MOD,}}}impl<const MOD: usize> ops::AddAssign for ModInt<MOD> {fn add_assign(&mut self, rhs: Self) {*self = *self + rhs;}}impl<const MOD: usize> ops::Mul for ModInt<MOD> {type Output = Self;fn mul(self, rhs: Self) -> Self::Output {Self {val: self.val * rhs.val % MOD,}}}impl<const MOD: usize> ops::MulAssign for ModInt<MOD> {fn mul_assign(&mut self, rhs: Self) {*self = *self * rhs;}}impl<const MOD: usize> ops::Sub for ModInt<MOD> {type Output = Self;fn sub(mut self, rhs: Self) -> Self::Output {if self.val < rhs.val {self.val += MOD;}Self {val: (self.val - rhs.val) % MOD,}}}impl<const MOD: usize> ops::SubAssign for ModInt<MOD> {fn sub_assign(&mut self, rhs: Self) {if self.val < rhs.val {self.val += MOD;}*self = *self - rhs;}}impl<const MOD: usize> ops::Div for ModInt<MOD> {type Output = Self;fn div(self, rhs: Self) -> Self {assert!(rhs.val != 0);self * rhs.pow(MOD - 2)}}impl<const MOD: usize> ops::DivAssign for ModInt<MOD> {fn div_assign(&mut self, rhs: Self) {*self = *self / rhs}}}use math::*;mod math {#[allow(dead_code)]pub fn pow(mut n: usize, mut e: usize, m: usize) -> usize {let mut res = 1;while 0 < e {if e & 1 != 0 {res *= n;res %= m;}n *= n;n %= m;e >>= 1;}res}#[allow(dead_code)]pub fn gcd(a: usize, b: usize) -> usize {if b == 0 {a} else {gcd(b, a % b)}}#[allow(dead_code)]pub fn lcm(a: usize, b: usize) -> usize {a / gcd(a, b) * b}#[allow(dead_code)]pub fn prime_factor(mut n: usize) -> std::collections::HashMap<usize, usize> {let mut pfacs = std::collections::HashMap::new();for d in 2.. {if d * d > n {break;}while n % d == 0 {*pfacs.entry(d).or_insert(0) += 1;n /= d;}}if n != 1 {*pfacs.entry(n).or_insert(0) += 1;}pfacs}#[allow(dead_code)]pub fn divisors(n: usize) -> Vec<usize> {let mut divs = vec![];for d in (1..).take_while(|&d| d * d <= n) {if n % d == 0 {divs.push(d);if n / d != d {divs.push(n / d);}}}divs}#[allow(dead_code)]pub fn eratosthenes_sieve(n: usize) -> Vec<usize> {let mut is_primes = vec![true; n + 1];is_primes[0] = false;is_primes[1] = false;let mut primes = vec![];for i in 2..=n {if !is_primes[i] {continue;}for j in (2 * i..=n).step_by(i) {is_primes[j] = false;}}for (val, is_prime) in is_primes.into_iter().enumerate() {if is_prime {primes.push(val);}}primes}#[allow(dead_code)]pub fn base_n(mut base10: usize, base: usize, len: usize) -> Vec<usize> {let mut base_n = vec![];for _ in 0..len {base_n.push(base10 % base);base10 /= base;}base_n.reverse();base_n}#[allow(dead_code)]pub fn div_floor(mut a: i64, mut b: i64) -> i64 {if b < 0 {a = -a;b = -b;}if a >= 0 {a / b} else {(a + 1) / b - 1}}#[allow(dead_code)]pub fn div_ceil(mut a: i64, mut b: i64) -> i64 {if b < 0 {a = -a;b = -b;}if a > 0 {(a - 1) / b + 1} else {a / b}}}