結果
問題 | No.1507 Road Blocked |
ユーザー |
![]() |
提出日時 | 2021-05-15 11:36:32 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 3,478 bytes |
コンパイル時間 | 12,445 ms |
コンパイル使用メモリ | 401,544 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-10-02 18:09:59 |
合計ジャッジ時間 | 15,500 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
pub mod mod_int {use std::{fmt, ops};#[derive(Clone, Copy, Debug)]pub struct ModInt(u64);impl ModInt {const MOD: u64 = 998_244_353;pub fn new(mut x: u64) -> Self {if x >= Self::MOD {x %= Self::MOD;}Self(x)}pub fn zero() -> Self {Self(0)}pub fn one() -> Self {Self(1)}}impl From<usize> for ModInt {fn from(x: usize) -> Self {Self::new(x as u64)}}impl From<i64> for ModInt {fn from(mut x: i64) -> Self {let m = Self::MOD as i64;if x.abs() >= m {x %= m;}if x < 0 {x += m}Self::new(x as u64)}}impl ops::Add for ModInt {type Output = Self;fn add(self, other: Self) -> Self {let mut x = self.0 + other.0;if x >= Self::MOD {x -= Self::MOD;}Self(x)}}impl ops::AddAssign for ModInt {fn add_assign(&mut self, other: Self) {*self = *self + other;}}impl ops::Sub for ModInt {type Output = Self;fn sub(mut self, other: Self) -> Self {if self.0 < other.0 {self.0 += Self::MOD;}Self(self.0 - other.0)}}impl ops::SubAssign for ModInt {fn sub_assign(&mut self, other: Self) {*self = *self - other;}}impl ops::Mul for ModInt {type Output = Self;fn mul(self, other: Self) -> Self {Self::new(self.0 * other.0)}}impl ops::MulAssign for ModInt {fn mul_assign(&mut self, other: Self) {*self = *self * other;}}impl fmt::Display for ModInt {fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {write!(f, "{}", self.0)}}impl ModInt {pub fn pow(mut self, mut n: u64) -> Self {let mut res = Self::one();while n > 0 {if n & 1 == 1 {res *= self;}self *= self;n >>= 1;}res}pub fn inv(self) -> Self {self.pow(Self::MOD - 2)}}}use mod_int::ModInt;fn dfs(ans: &mut ModInt,n: usize, g: &[Vec<usize>], p: ModInt,prev: usize, from: usize) -> usize {let mut count = 0;for &to in &g[from] {if to == prev { continue; }let c = dfs(ans, n, g, p, from, to);*ans = *ans - ModInt::from(c * (n - c)) * p;count += c;}count + 1}fn main() {let ref mut buf = String::new();std::io::Read::read_to_string(&mut std::io::stdin(), buf).ok();let mut iter = buf.split_whitespace();macro_rules! scan {($t:ty) => (iter.next().unwrap().parse::<$t>().unwrap());}let n = scan!(usize);let mut g = vec![vec![]; n];for _ in 0..(n - 1) {let (u, v) = (scan!(usize) - 1, scan!(usize) - 1);g[u].push(v);g[v].push(u);}let mut ans = ModInt::one();let k = n * (n - 1) / 2;let p = ModInt::from((n - 1) * k).inv();dfs(&mut ans, n, &g, p, !0, 0);println!("{}", ans);}