結果
問題 | No.2007 Arbitrary Mod (Easy) |
ユーザー | tayu0110 |
提出日時 | 2022-10-22 00:38:34 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 9,541 bytes |
コンパイル時間 | 12,318 ms |
コンパイル使用メモリ | 400,916 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:35:44 |
合計ジャッジ時間 | 15,314 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,944 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,940 KB |
testcase_10 | AC | 1 ms
6,940 KB |
testcase_11 | AC | 1 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,940 KB |
testcase_13 | AC | 1 ms
6,940 KB |
testcase_14 | AC | 1 ms
6,944 KB |
testcase_15 | AC | 1 ms
6,940 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 1 ms
6,940 KB |
testcase_19 | AC | 1 ms
6,940 KB |
testcase_20 | AC | 1 ms
6,940 KB |
testcase_21 | AC | 1 ms
6,944 KB |
testcase_22 | AC | 1 ms
6,940 KB |
testcase_23 | AC | 1 ms
6,944 KB |
testcase_24 | AC | 1 ms
6,940 KB |
testcase_25 | AC | 1 ms
6,944 KB |
testcase_26 | AC | 1 ms
6,944 KB |
testcase_27 | AC | 1 ms
6,944 KB |
testcase_28 | AC | 1 ms
6,944 KB |
testcase_29 | AC | 1 ms
6,944 KB |
testcase_30 | AC | 1 ms
6,940 KB |
testcase_31 | AC | 1 ms
6,940 KB |
testcase_32 | AC | 1 ms
6,944 KB |
ソースコード
use crate::modint::Modulo; type Mint = modint::Mint<modint::Mod998244353>; fn main() { scan!(a: i64, n: i64); println!("{}", modint::Mod998244353::modulo()); println!("{}", Mint::raw(a).pow(n)); } #[allow(dead_code)] pub mod modint { use std::marker; use std::ops; pub trait Modulo { fn modulo() -> i64; fn primitive_root() -> i64; } #[derive(Clone, marker::Copy)] pub enum Mod998244353 {} impl Modulo for Mod998244353 { fn modulo() -> i64 { 998_244_353i64 } fn primitive_root() -> i64 { 3i64 } } #[derive(Clone, marker::Copy)] pub enum Mod1000000007 {} impl Modulo for Mod1000000007 { fn modulo() -> i64 { 1_000_000_007i64 } fn primitive_root() -> i64 { unimplemented!(); } } #[derive(Clone, Copy, PartialEq, Eq)] pub struct Mint<M> where M: Modulo { val: i64, _p: marker::PhantomData<M> } impl<M> Mint<M> where M: Modulo + marker::Copy { pub fn new(val: i64) -> Self { Mint { val: (val % M::modulo() + M::modulo()) % M::modulo(), _p: marker::PhantomData } } pub fn raw(val: i64) -> Self { assert!(0 <= val && val < M::modulo()); Mint { val, _p: marker::PhantomData } } pub fn zero() -> Self { Mint { val: 0i64, _p: marker::PhantomData } } pub fn one() -> Self { Mint { val: 1i64, _p: marker::PhantomData } } pub fn modulo() -> i64 { M::modulo() } pub fn val(&self) -> i64 { self.val } pub fn pow(&self, mut exp: i64) -> Self { let (mut val, mut res) = (self.val, 1); while exp > 0 { if exp % 2 == 1 { res = (res * val) % M::modulo(); } val = (val * val) % M::modulo(); exp >>= 1; } Self { val: res, _p: marker::PhantomData } } pub fn inv(&self) -> Self { self.pow(M::modulo() - 2) } pub fn nth_root(n: i64) -> Self { assert!(n.abs() == 1 << n.abs().trailing_zeros()); assert!(M::modulo() - 1 + (M::modulo() - 1) / n >= 0); Mint::raw(M::primitive_root()).pow(M::modulo() - 1 + (M::modulo() - 1) / n) } pub fn add_raw(&self, rhs: i64) -> Self { *self + Mint::new(rhs) } pub fn sub_raw(&self, rhs: i64) -> Self { *self - Mint::new(rhs) } pub fn mul_raw(&self, rhs: i64) -> Self { *self * Mint::new(rhs) } pub fn div_raw(&self, rhs: i64) -> Self { *self / Mint::new(rhs) } } impl<M> Default for Mint<M> where M: Modulo + marker::Copy { fn default() -> Self { Mint::zero() } } impl<M> std::fmt::Debug for Mint<M> where M: Modulo + marker::Copy { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.val) } } impl<M> std::fmt::Display for Mint<M> where M: Modulo + marker::Copy { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.val) } } impl<M> ops::Add for Mint<M> where M: Modulo + marker::Copy { type Output = Self; fn add(self, rhs: Self) -> Self::Output { Self::new(self.val + rhs.val) } } impl<M> ops::AddAssign for Mint<M> where M: Modulo + marker::Copy { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl<M> ops::Sub for Mint<M> where M: Modulo + marker::Copy { type Output = Self; fn sub(self, rhs: Self) -> Self::Output { Self::new(self.val - rhs.val + M::modulo()) } } impl<M> ops::SubAssign for Mint<M> where M: Modulo + marker::Copy { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl<M> ops::Mul for Mint<M> where M: Modulo + marker::Copy { type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Self::new(self.val * rhs.val) } } impl<M> ops::MulAssign for Mint<M> where M: Modulo + marker::Copy { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl<M> ops::Div for Mint<M> where M: Modulo + marker::Copy { type Output = Self; fn div(self, rhs: Self) -> Self::Output { assert!(rhs.val != 0); self * rhs.inv() } } impl<M> ops::DivAssign for Mint<M> where M: Modulo + marker::Copy { fn div_assign(&mut self, rhs: Self) { assert!(rhs.val != 0); *self *= rhs.inv() } } pub struct Combination<M> where M: Modulo { fact: Vec<Mint<M>>, ifact: Vec<Mint<M>> } impl<M> Combination<M> where M: Modulo + marker::Copy { pub fn new(size: usize) -> Self { let mut fact = vec![Mint::one(); size+1]; let mut ifact = vec![Mint::one(); size+1]; let mut buf = vec![Mint::one(); size+1]; fact.iter_mut().enumerate().skip(1).for_each(|(i, v)| { *v = buf[i-1] * Mint::raw(i as i64); buf[i] = *v; }); ifact[size] = fact[size].inv(); buf[size] = ifact[size]; ifact.iter_mut().enumerate().skip(1).rev().skip(1).for_each(|(i, v)| { *v = buf[i+1] * Mint::raw(i as i64 + 1); buf[i] = *v; }); Self { fact, ifact } } pub fn get(&self, n: usize, k: usize) -> Mint<M> { if n < k { Mint::zero() } else { self.fact[n] * self.ifact[k] * self.ifact[n-k] } } } } mod iolib { use std::cell::RefCell; use std::io::{ Read, BufRead, Error }; use std::str::SplitWhitespace; use std::thread_local; thread_local! { static BUF_SPLIT_WHITESPACE: RefCell<SplitWhitespace<'static>> = RefCell::new("".split_whitespace()); } #[inline] fn refill_buffer(interactive: bool) -> Result<(), Error> { let mut s = String::new(); if cfg!(debug_assertions) || interactive { std::io::stdin().lock().read_line(&mut s)?; } else { std::io::stdin().lock().read_to_string(&mut s)?; } BUF_SPLIT_WHITESPACE.with(|buf_str| { *buf_str.borrow_mut() = Box::leak(s.into_boxed_str()).split_whitespace(); Ok(()) }) } #[inline] pub fn scan_string(interactive: bool) -> &'static str { BUF_SPLIT_WHITESPACE.with(|buf_str| { if let Some(s) = buf_str.borrow_mut().next() { return s; } refill_buffer(interactive).unwrap(); if let Some(s) = buf_str.borrow_mut().next() { return s; } unreachable!("Read Error: No input items."); }) } #[macro_export] macro_rules! scan { // Terminator ( @interactive : $interactive:literal ) => {}; // Terminator ( @interactive : $interactive:literal, ) => {}; // Vec<Vec<....>> ( @interactive : $interactive:literal, $v: ident : [ [ $( $inner:tt )+ ] ; $len:expr ]) => { let $v = { let len = $len; (0..len).fold(vec![], |mut v, _| { $crate::scan!(@interactive: $interactive, w: [ $( $inner )+ ]); v.push(w); v }) }; }; // Vec<Vec<....>>, ...... ( @interactive : $interactive:literal, $v: ident : [ [ $( $inner:tt )+ ] ; $len:expr ] , $( $rest:tt )* ) => { $crate::scan!(@interactive: $interactive, [ [ $( $inner )+ ] ; $len ]); $crate::scan!(@interactive: $interactive, $( $rest )*); }; // Vec<$t> ( @interactive : $interactive:literal, $v:ident : [ $t:tt ; $len:expr ]) => { let $v = { let len = $len; (0..len).map(|_| { $crate::scan!(@interactive: $interactive, $v : $t); $v }).collect::<Vec<_>>() }; }; // Vec<$t>, ..... ( @interactive : $interactive:literal, $v:ident : [ $t:tt ; $len:expr ] , $( $rest:tt )* ) => { let $v = { let len = $len; (0..len).map(|_| { $crate::scan!(@interactive: $interactive, $v : $t); $v }).collect::<Vec<_>>() }; $crate::scan!(@interactive: $interactive, $( $rest )*); }; // Expand tuple ( @interactive : $interactive:literal, @expandtuple, ( $t:tt )) => { { let tmp = $crate::iolib::scan_string($interactive).parse::<$t>().unwrap(); tmp } }; // Expand tuple ( @interactive : $interactive:literal, @expandtuple, ( $t:tt $( , $rest:tt )* ) ) => { ( $crate::scan!(@interactive: $interactive, @expandtuple, ( $t )), $( $crate::scan!(@interactive: $interactive, @expandtuple, ( $rest )), )* ) }; // let $v: ($t, $u, ....) = (.......) ( @interactive : $interactive:literal, $v:ident : ( $( $rest:tt )* ) ) => { let $v = $crate::scan!(@interactive: $interactive, @expandtuple, ( $( $rest )* )); }; // let $v: $t = ...... ( @interactive : $interactive:literal, $v:ident : $t:ty ) => { let $v = $crate::iolib::scan_string($interactive).parse::<$t>().unwrap(); }; // let $v: $t = ......, ....... ( @interactive : $interactive:literal, $v:ident : $t:ty, $( $rest:tt )+ ) => { $crate::scan!(@interactive: $interactive, $v : $t); $crate::scan!(@interactive: $interactive, $( $rest )+); }; // ...... ( $( $rest:tt )* ) => { $crate::scan!(@interactive: false, $( $rest )*); }; } #[macro_export] macro_rules! scani { ( $( $rest:tt )* ) => { $crate::scan!(@interactive: true, $( $rest )*); }; } }