結果

問題 No.2733 Just K-times TSP
コンテスト
ユーザー magurofly
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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); } }
0