#809837 (Rust) No.2007 Arbitrary Mod (Easy)

• 問題: No.2007 Arbitrary Mod (Easy)
• ユーザー: tayu0110
• 提出日時: 2022-10-22 00:38:34
• 言語: Rust (1.83.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

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

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 )*);
        };
    }
}