結果
| 問題 | No.502 階乗を計算するだけ |
| コンテスト | |
| ユーザー |
 guricerin
|
| 提出日時 | 2019-07-07 10:17:02 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 15,096 bytes |
| 記録 | |
| コンパイル時間 | 13,979 ms |
| コンパイル使用メモリ | 391,332 KB |
| 実行使用メモリ | 812,984 KB |
| 最終ジャッジ日時 | 2024-10-04 04:33:45 |
| 合計ジャッジ時間 | 16,605 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 32 MLE * 1 -- * 19 |
ソースコード
// Original: https://github.com/tanakh/competitive-rs
#[allow(unused_macros)]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
let mut $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, [ $t:tt ]) => {
{
let len = read_value!($next, usize);
(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
}
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, bytes) => {
read_value!($next, String).into_bytes()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
#[allow(dead_code)]
fn chmin<T>(x: &mut T, y: T) -> bool
where
T: PartialOrd + Copy,
{
*x > y && {
*x = y;
true
}
}
#[allow(dead_code)]
fn chmax<T>(x: &mut T, y: T) -> bool
where
T: PartialOrd + Copy,
{
*x < y && {
*x = y;
true
}
}
mod mint {
use std::fmt;
use std::marker::PhantomData;
use std::mem;
use std::ops;
#[doc = " Trait for `Mint`. `module()` should return prime number."]
pub trait Module: Copy + Clone {
fn module() -> u32;
}
#[doc = " One of famous numbers in programming contest. `10^9 + 7`"]
pub const MOD_107: u32 = 1_000_000_007;
#[doc = " One of famous numbers in programming contest. `10^9 + 9`"]
pub const MOD_109: u32 = 1_000_000_009;
#[doc = " One of famous numbers in programming contest. `998_244_353`"]
pub const MOD_998: u32 = 998_244_353;
#[doc = " struct to implement Module trait. it returns `MOD_107`."]
#[derive(Debug, Copy, Clone)]
pub struct Mod107;
impl Module for Mod107 {
fn module() -> u32 {
MOD_107
}
}
#[doc = " struct to implement Module trait. it returns `MOD_109`."]
#[derive(Debug, Copy, Clone)]
pub struct Mod109;
impl Module for Mod109 {
fn module() -> u32 {
MOD_109
}
}
#[doc = " struct to implement Module trait. it returns `MOD_998`."]
#[derive(Debug, Copy, Clone)]
pub struct Mod998;
impl Module for Mod998 {
fn module() -> u32 {
MOD_998
}
}
#[doc = " Wrapper class to compute mod `1_000_000_007` automatically."]
#[doc = ""]
#[doc = " # Examples"]
#[doc = " ```"]
#[doc = " use algonium::math::{Mint107, MOD_107};"]
#[doc = " let x: Mint107 = 1234567.into();"]
#[doc = " let y: Mint107 = 2345678.into();"]
#[doc = " let z = x * y;"]
#[doc = " # // TODO: implement convert to u64"]
#[doc = " assert_eq!(z.val as u64, 1234567u64 * 2345678u64 % MOD_107 as u64);"]
#[doc = " ```"]
#[doc = ""]
pub type Mint107 = Mint<Mod107>;
#[doc = " Wrapper class to compute mod `1_000_000_009` automatically."]
#[doc = ""]
#[doc = " # Examples"]
#[doc = " ```"]
#[doc = " use algonium::math::{Mint109, MOD_109};"]
#[doc = " let x: Mint109 = 1234567.into();"]
#[doc = " let y: Mint109 = 2345678.into();"]
#[doc = " let z = x * y;"]
#[doc = " assert_eq!(z.val as u64, 1234567u64 * 2345678u64 % MOD_109 as u64);"]
#[doc = " ```"]
#[doc = ""]
pub type Mint109 = Mint<Mod109>;
#[doc = " Wrapper class to compute mod `998_244_353` automatically."]
#[doc = ""]
#[doc = " # Examples"]
#[doc = " ```"]
#[doc = " use algonium::math::{Mint998, MOD_998};"]
#[doc = " let x: Mint998 = 1234567.into();"]
#[doc = " let y: Mint998 = 2345678.into();"]
#[doc = " let z = x * y;"]
#[doc = " assert_eq!(z.val as u64, 1234567u64 * 2345678u64 % MOD_998 as u64);"]
#[doc = " ```"]
#[doc = ""]
pub type Mint998 = Mint<Mod998>;
#[doc = " Wrapper class to compute modulo operation."]
#[doc = " See examples"]
#[doc = " [`Mint107`](type.Mint107.html),"]
#[doc = " [`Mint109`](type.Mint109.html),"]
#[doc = " [`Mint998`](type.Mint998.html)"]
#[doc = ""]
#[doc = " # Examples"]
#[doc = " ```"]
#[doc = " use algonium::math::{Mint107, MOD_107};"]
#[doc = " let x: Mint107 = 1234567.into();"]
#[doc = " let y: Mint107 = 2345678.into();"]
#[doc = " let z = x * y;"]
#[doc = " assert_eq!(z.val as u64, 1234567u64 * 2345678u64 % MOD_107 as u64);"]
#[doc = " ```"]
#[derive(Debug, Copy, Clone, Eq)]
pub struct Mint<M: Module> {
#[doc = " internal value. this is always less than `self.module()`."]
pub val: u32,
m: PhantomData<M>,
}
impl<M: Module> Mint<M> {
fn module(self) -> u32 {
M::module()
}
fn new(val: u32) -> Mint<M> {
assert!(val < M::module());
Mint {
val: val,
m: PhantomData,
}
}
}
impl<T: Into<Mint<M>>, M: Module> ops::Add<T> for Mint<M> {
type Output = Mint<M>;
fn add(self, other: T) -> Mint<M> {
let nval = self.val + other.into().val;
Mint::new(if nval >= self.module() {
nval - self.module()
} else {
nval
})
}
}
impl<T: Into<Mint<M>>, M: Module> ops::Sub<T> for Mint<M> {
type Output = Mint<M>;
fn sub(self, other: T) -> Mint<M> {
let nval = self.val + self.module() - other.into().val;
Mint::new(if nval >= self.module() {
nval - self.module()
} else {
nval
})
}
}
impl<T: Into<Mint<M>>, M: Module> ops::Mul<T> for Mint<M> {
type Output = Mint<M>;
fn mul(self, other: T) -> Mint<M> {
let nval = self.val as u64 * other.into().val as u64;
Mint::new((nval % (self.module() as u64)) as u32)
}
}
impl<T: Into<Mint<M>>, M: Module> ops::Div<T> for Mint<M> {
type Output = Mint<M>;
fn div(self, other: T) -> Mint<M> {
self * other.into().inv()
}
}
impl<M: Module> Mint<M> {
#[doc = " Returns number `y` that satisfies `x * y == 1` where `x` is the original value."]
#[doc = ""]
#[doc = " This assumes `module()` returns prime number."]
pub fn inv(self) -> Mint<M> {
let mut a = self.val as i32;
let mut b = self.module() as i32;
let mut u = 1 as i32;
let mut v = 0 as i32;
while b != 0 {
let t = a / b;
a -= t * b;
mem::swap(&mut a, &mut b);
u -= t * v;
mem::swap(&mut u, &mut v);
}
Mint::new(if u < 0 { u + self.module() as i32 } else { u } as u32)
}
}
impl<M: Module> PartialEq for Mint<M> {
fn eq(&self, other: &Mint<M>) -> bool {
self.val == other.val
}
}
impl<M: Module> fmt::Display for Mint<M> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.val.fmt(f)
}
}
macro_rules ! impl_signed_mint { ( $ ( $ t : ty ) * ) => ( $ ( impl < M : Module > From <$ t > for Mint < M > { # [ inline ] fn from ( x : $ t ) -> Mint < M > { let t = ( x as i64 ) % ( M :: module ( ) as i64 ) ; if x >= 0 { Mint { val : t as u32 , m : PhantomData } } else { Mint { val : ( M :: module ( ) as i64 + t ) as u32 , m : PhantomData } } } } ) * ) }
macro_rules ! impl_unsigned_mint { ( $ ( $ t : ty ) * ) => ( $ ( impl < M : Module > From <$ t > for Mint < M > { # [ inline ] fn from ( x : $ t ) -> Mint < M > { let t = x as u64 % M :: module ( ) as u64 ; Mint :: new ( t as u32 ) } } ) * ) }
impl_signed_mint! { i8 i16 i32 i64 isize }
impl_unsigned_mint! { u8 u16 u32 u64 usize }
impl<T: Into<Mint<M>>, M: Module> ops::AddAssign<T> for Mint<M> {
fn add_assign(&mut self, other: T) {
*self = *self + other.into();
}
}
impl<T: Into<Mint<M>>, M: Module> ops::SubAssign<T> for Mint<M> {
fn sub_assign(&mut self, other: T) {
*self = *self - other.into();
}
}
impl<T: Into<Mint<M>>, M: Module> ops::MulAssign<T> for Mint<M> {
fn mul_assign(&mut self, other: T) {
*self = *self * other.into();
}
}
impl<T: Into<Mint<M>>, M: Module> ops::DivAssign<T> for Mint<M> {
fn div_assign(&mut self, other: T) {
*self = *self / other.into();
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_simple() {
let a: Mint<Mod107> = Mint::from(3);
let b: Mint<Mod107> = Mint::from(1000000000);
assert_eq!(Mint::from(3000000000u64 % Mod107::module() as u64), a * b);
}
}
}
mod comb {
use super::mint::{Mint, Module};
#[doc = " Useful struct to compute combinations"]
#[doc = ""]
#[doc = " # Examples"]
#[doc = " ```"]
#[doc = " use algonium::math::{Comb, Mod107, Mint107};"]
#[doc = " let comb: Comb<Mod107> = Comb::new(100);"]
#[doc = " assert_eq!(Mint107::from(24), comb.fact(4));"]
#[doc = " assert_eq!(Mint107::from(1), comb.fact(4) * comb.factinv(4));"]
#[doc = " assert_eq!(Mint107::from(12), comb.perm(4, 2));"]
#[doc = " assert_eq!(Mint107::from(6), comb.comb(4, 2));"]
#[doc = " assert_eq!(Mint107::from(10), comb.multi_comb(4, 2));"]
#[doc = " ```"]
pub struct Comb<M: Module> {
fact: Vec<Mint<M>>,
factinv: Vec<Mint<M>>,
}
impl<M: Module> Comb<M> {
#[doc = " Create a object that provides effiecint computation of combinations"]
#[doc = " for input smaller than `n`."]
#[doc = ""]
#[doc = " This requires `O(n)` time."]
pub fn new(n: usize) -> Comb<M> {
let mut fact: Vec<Mint<M>> = vec![0.into(); n + 1];
let mut factinv: Vec<Mint<M>> = vec![0.into(); n + 1];
fact[0] = 1.into();
for i in 0..n {
fact[i + 1] = fact[i] * (i + 1);
}
factinv[n] = fact[n].inv();
for i in (0..n).rev() {
factinv[i] = factinv[i + 1] * (i + 1);
}
Comb {
fact: fact,
factinv: factinv,
}
}
#[doc = " `n! = 1 * 2 * ... * n`"]
#[doc = ""]
#[doc = " `O(1)` if n is smaller than input in `new` method."]
pub fn fact(&self, n: u64) -> Mint<M> {
if let Some(x) = self.fact.get(n as usize) {
*x
} else if n >= M::module() as u64 {
Mint::from(0)
} else {
let mut res = 1.into();
for a in 1..(n + 1) {
res *= a;
}
res
}
}
#[doc = " returns `y` such that `n! * y == 1`."]
#[doc = ""]
#[doc = " `O(1)` if n is smaller than input in `new` method."]
pub fn factinv(&self, n: u64) -> Mint<M> {
if let Some(x) = self.factinv.get(n as usize) {
*x
} else {
self.fact(n).inv()
}
}
#[doc = " `nPr = n! / (n - r)!`"]
#[doc = ""]
#[doc = " `O(1)` if n and r are smaller than input in `new` method."]
pub fn perm(&self, n: u64, r: u64) -> Mint<M> {
if n >= r {
self.fact(n) * self.factinv((n - r) as u64)
} else {
0.into()
}
}
#[doc = " `nCr = n! / (n - r)! / r!`."]
#[doc = ""]
#[doc = " `O(1)` if n and r are smaller than input in `new` method."]
pub fn comb(&self, n: u64, r: u64) -> Mint<M> {
let m = M::module() as u64;
if n >= m {
self.comb(n % m, r % m) * self.comb(n / m, r / m)
} else if n >= r {
self.fact(n) * self.factinv(n - r) * self.factinv(r)
} else {
Mint::from(0)
}
}
#[doc = " `(n + k - 1)! / k!`."]
#[doc = ""]
#[doc = " `O(1)` if n and r are smaller than input in `new` method."]
pub fn multi_comb(&self, n: u64, r: u64) -> Mint<M> {
if r == 0 {
Mint::from(1)
} else {
self.comb(n + r - 1, r)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_simple() {
#[derive(Clone, Copy, Debug)]
struct Mod;
impl Module for Mod {
fn module() -> u32 {
1000000007
}
}
let c = Comb::<Mod>::new(100);
assert_eq!(Mint::from(336), c.perm(8, 3));
assert_eq!(Mint::from(56), c.comb(8, 3));
assert_eq!(Mint::from(10), c.multi_comb(3, 3));
}
#[test]
fn test_fact() {
#[derive(Clone, Copy, Debug)]
struct Mod;
impl Module for Mod {
fn module() -> u32 {
1000000007
}
}
let c = Comb::<Mod>::new(100);
let p = 8721234;
let mut f = Mint::from(1);
for i in 1..(p + 1) {
f *= i;
}
assert_eq!(f, c.fact(p));
}
}
}
pub use self::comb::Comb;
pub use self::mint::{Mint, Module};
pub use self::mint::{Mint107, Mint109, Mint998};
pub use self::mint::{Mod107, Mod109, Mod998};
pub use self::mint::{MOD_107, MOD_109, MOD_998};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, VecDeque};
fn main() {
input!(n: u64);
if n >= MOD_107 as u64 {
println!("0");
} else {
let a = Comb::<Mod107>::new(n as usize);
println!("{}", a.fact(n));
}
}