結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2020-11-27 21:44:02 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 13 ms / 3,000 ms |
コード長 | 5,436 bytes |
コンパイル時間 | 24,565 ms |
コンパイル使用メモリ | 399,732 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-26 12:05:42 |
合計ジャッジ時間 | 14,694 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
コンパイルメッセージ
warning: methods `perm` and `homo` are never used --> src/main.rs:205:12 | 179 | impl FpUtility { | -------------- methods in this implementation ... 205 | pub fn perm(&self, n: usize, r: usize) -> Fp { | ^^^^ ... 213 | pub fn homo(&self, n: usize, r: usize) -> Fp { | ^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
use std::io::{self, Read as _, Write as _};struct Scanner<'a>(std::str::SplitWhitespace<'a>);impl<'a> Scanner<'a> {fn new(s: &'a str) -> Self {Self(s.split_whitespace())}fn next<T>(&mut self) -> TwhereT: std::str::FromStr,T::Err: std::fmt::Debug,{let s = self.0.next().expect("found EOF");match s.parse() {Ok(v) => v,Err(msg) => {println!("parse error. T = {}, s = \"{}\": {:?}",std::any::type_name::<T>(),s,msg);panic!()}}}}pub mod fp {use std::convert::From;use std::iter;use std::ops;pub const P: u32 = 998244353;#[derive(Copy, Clone, Debug)]pub struct Fp(pub u32);impl Fp {pub fn pow(mut self, mut exp: u32) -> Fp {let mut res = Fp(1);while exp != 0 {if exp % 2 != 0 {res *= self;}self *= self;exp /= 2;}res}}impl From<i64> for Fp {fn from(mut x: i64) -> Fp {x %= P as i64;if x < 0 {x += P as i64;}Fp(x as u32)}}impl iter::Product for Fp {fn product<I>(iter: I) -> FpwhereI: Iterator<Item = Fp>,{iter.fold(Fp(1), |b, i| b * i)}}impl iter::Sum for Fp {fn sum<I>(iter: I) -> FpwhereI: Iterator<Item = Fp>,{iter.fold(Fp(0), |b, i| b + i)}}impl ops::Add<Fp> for Fp {type Output = Fp;fn add(mut self, rhs: Fp) -> Fp {self += rhs;self}}impl ops::AddAssign<Fp> for Fp {fn add_assign(&mut self, rhs: Fp) {self.0 += rhs.0;if self.0 >= P {self.0 -= P;}}}impl ops::Mul<Fp> for Fp {type Output = Fp;fn mul(mut self, rhs: Fp) -> Fp {self *= rhs;self}}impl ops::MulAssign<Fp> for Fp {fn mul_assign(&mut self, rhs: Fp) {self.0 = (self.0 as u64 * rhs.0 as u64 % P as u64) as u32;}}impl ops::Neg for Fp {type Output = Fp;fn neg(self) -> Fp {Fp(match self.0 {0 => 0,s => P - s,})}}impl ops::Sub<Fp> for Fp {type Output = Fp;fn sub(mut self, rhs: Fp) -> Fp {self -= rhs;self}}impl ops::SubAssign<Fp> for Fp {fn sub_assign(&mut self, rhs: Fp) {if self.0 < rhs.0 {self.0 += P;}self.0 -= rhs.0;}}impl ops::Div<Fp> for Fp {type Output = Fp;fn div(self, rhs: Fp) -> Fp {self * Fp::pow(rhs, P - 2)}}impl ops::DivAssign<Fp> for Fp {fn div_assign(&mut self, rhs: Fp) {*self = *self / rhs;}}use std::str::FromStr;impl FromStr for Fp {type Err = <u32 as FromStr>::Err;fn from_str(s: &str) -> Result<Fp, <Fp as FromStr>::Err> {u32::from_str(s).map(|x| Fp(x))}}use std::fmt;impl fmt::Display for Fp {fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {self.0.fmt(f)}}}use fp::Fp;struct FpUtility {fact_: Box<[Fp]>,inv_fact_: Box<[Fp]>,}impl FpUtility {pub fn new(n: usize) -> Self {let mut fact_ = vec![Fp(0); n + 1];let mut inv_fact_ = vec![Fp(0); n + 1];fact_[0] = Fp(1);for i in 1..=n {fact_[i] = fact_[i - 1] * Fp(i as u32);}inv_fact_[n] = Fp(1) / fact_[n];for i in (1..=n).rev() {inv_fact_[i - 1] = inv_fact_[i] * Fp(i as u32);}Self {fact_: fact_.into_boxed_slice(),inv_fact_: inv_fact_.into_boxed_slice(),}}pub fn fact(&self, n: usize) -> Fp {self.fact_[n]}pub fn inv_fact(&self, n: usize) -> Fp {self.inv_fact_[n]}pub fn perm(&self, n: usize, r: usize) -> Fp {self.fact_[n] * self.inv_fact_[n - r]}pub fn binom(&self, n: usize, r: usize) -> Fp {self.fact_[n] * self.inv_fact_[r] * self.inv_fact_[n - r]}pub fn homo(&self, n: usize, r: usize) -> Fp {self.fact_[n + r - 1] * self.inv_fact_[r] * self.inv_fact_[n - 1]}}fn main() {let mut stdin = String::new();std::io::stdin().read_to_string(&mut stdin).unwrap();let mut sc = Scanner::new(&stdin);let stdout = io::stdout();let mut stdout = io::BufWriter::new(stdout.lock());// writeln!(stdout, "");let n: usize = sc.next();let c = FpUtility::new(n);let mut ans = Fp(0);for k in 0..=n - 2 {let l = n - 2 - k;ans += c.binom(n, k) * Fp(n as u32).pow(l as u32) * c.inv_fact(l);}writeln!(stdout,"{}",ans * c.fact(n - 2) / Fp(n as u32).pow((n - 2) as u32)).unwrap();stdout.flush().unwrap();}