#681874 (Rust) No.1620 Substring Sum

提出ソース
結果

問題	No.1620 Substring Sum
ユーザー	cotton_fn_
提出日時	2021-07-22 22:25:27
言語	Rust (1.77.0)
結果	AC
実行時間	36 ms / 2,000 ms
コード長	15,682 bytes
コンパイル時間	4,995 ms
コンパイル使用メモリ	158,160 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-24 17:35:18
合計ジャッジ時間	3,077 ms
ジャッジサーバーID （参考情報）	judge11 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	36 ms 4,376 KB
testcase_05	AC	36 ms 4,376 KB
testcase_06	AC	35 ms 4,376 KB
testcase_07	AC	35 ms 4,380 KB
testcase_08	AC	35 ms 4,376 KB
testcase_09	AC	34 ms 4,380 KB
testcase_10	AC	35 ms 4,376 KB
testcase_11	AC	35 ms 4,376 KB
testcase_12	AC	11 ms 4,380 KB
testcase_13	AC	32 ms 4,376 KB
testcase_14	AC	33 ms 4,376 KB
testcase_15	AC	28 ms 4,376 KB
testcase_16	AC	19 ms 4,380 KB
testcase_17	AC	28 ms 4,376 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,380 KB
testcase_20	AC	35 ms 4,380 KB
testcase_21	AC	36 ms 4,380 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(unused_imports)]
use pio2::*;
use std::{
    collections::*,
    io::{self, prelude::*},
};
def_mint!(998244353, Mod);
fn run<I: Input, O: Write>(mut pin: I, mut out: O) {
    use mod_int::*;
    let s = pin.bytes();
    let n = s.len();
    let mut ans = mint(0);
    for (i, c) in s.iter().rev().enumerate() {
        ans += mint(2).pow(n - i - 1) * mint(11).pow(i) * Mint::from(c - b'0');
    }
    wln!(out, "{}", ans);
}
fn main() {
    let stdin = io::stdin();
    let mut pin = Scanner::new(stdin.lock());
    let stdout = io::stdout();
    let mut out = stdout.lock();
    run(&mut pin, &mut out);
}
pub mod mod_int {
    use std::{cmp, fmt, marker::PhantomData, ops, sync::atomic};
    #[macro_export]
    macro_rules! def_mint {
        ($modulo:expr, $ModuloTy:ident) => {
            pub struct $ModuloTy;
            impl crate::mod_int::Modulo for $ModuloTy {
                fn modulo() -> u32 {
                    $modulo
                }
            }
            pub type Mint = crate::mod_int::ModInt<$ModuloTy>;
            pub fn mint(x: u32) -> Mint {
                crate::mod_int::ModInt::new(x)
            }
        };
    }
    pub trait Modulo {
        fn modulo() -> u32;
    }
    pub struct VarMod;
    static VAR_MOD: atomic::AtomicU32 = atomic::AtomicU32::new(0);
    pub fn set_var_mod(m: u32) {
        VAR_MOD.store(m, atomic::Ordering::Relaxed);
    }
    impl Modulo for VarMod {
        fn modulo() -> u32 {
            VAR_MOD.load(atomic::Ordering::Relaxed)
        }
    }
    #[repr(transparent)]
    pub struct ModInt<M>(u32, PhantomData<*const M>);
    impl<M: Modulo> ModInt<M> {
        pub fn new(x: u32) -> Self {
            debug_assert!(x < M::modulo());
            Self(x, PhantomData)
        }
        pub fn normalize(self) -> Self {
            if self.0 < M::modulo() {
                self
            } else {
                Self::new(self.0 % M::modulo())
            }
        }
        pub fn get(self) -> u32 {
            self.0
        }
        pub fn inv(self) -> Self {
            assert_ne!(self, Self::new(0));
            self.pow(M::modulo() - 2)
        }
        pub fn half(self) -> Self {
            Self::new(self.0 / 2 + self.0 % 2 * ((M::modulo() + 1) / 2))
        }
        pub fn modulo() -> u32 {
            M::modulo()
        }
    }
    impl<M: Modulo> ops::Neg for ModInt<M> {
        type Output = Self;
        fn neg(self) -> Self {
            Self::new(if self.0 == 0 { 0 } else { M::modulo() - self.0 })
        }
    }
    impl<M: Modulo> ops::Neg for &'_ ModInt<M> {
        type Output = ModInt<M>;
        fn neg(self) -> Self::Output {
            -(*self)
        }
    }
    impl<M: Modulo> ops::Add for ModInt<M> {
        type Output = Self;
        fn add(self, rhs: Self) -> Self {
            let s = self.0 + rhs.0;
            Self::new(if s < M::modulo() { s } else { s - M::modulo() })
        }
    }
    impl<M: Modulo> ops::Sub for ModInt<M> {
        type Output = Self;
        fn sub(self, rhs: Self) -> Self {
            Self::new(if self.0 >= rhs.0 {
                self.0 - rhs.0
            } else {
                M::modulo() + self.0 - rhs.0
            })
        }
    }
    impl<M: Modulo> ops::Mul for ModInt<M> {
        type Output = Self;
        fn mul(self, rhs: Self) -> Self {
            Self::new((self.0 as u64 * rhs.0 as u64 % M::modulo() as u64) as u32)
        }
    }
    impl<M: Modulo> ops::Div for ModInt<M> {
        type Output = Self;
        fn div(self, rhs: Self) -> Self {
            self * rhs.inv()
        }
    }
    macro_rules ! op_impl { ($ ($ Op : ident $ op : ident $ OpAssign : ident $ op_assign : ident) *) => { $ (impl < M : Modulo > ops ::$ Op <& Self > for ModInt < M > { type Output = Self ; fn $ op (self , rhs : & Self) -> Self { self .$ op (* rhs) } } impl < M : Modulo > ops ::$ Op < ModInt < M >> for & ModInt < M > { type Output = ModInt < M >; fn $ op (self , rhs : ModInt < M >) -> ModInt < M > { (* self) .$ op (rhs) } } impl < M : Modulo > ops ::$ Op <& ModInt < M >> for & ModInt < M > { type Output = ModInt < M >; fn $ op (self , rhs : & ModInt < M >) -> ModInt < M > { (* self) .$ op (* rhs) } } impl < M : Modulo > ops ::$ OpAssign for ModInt < M > { fn $ op_assign (& mut self , rhs : Self) { * self = ops ::$ Op ::$ op (* self , rhs) ; } } impl < M : Modulo > ops ::$ OpAssign <& ModInt < M >> for ModInt < M > { fn $ op_assign (& mut self , rhs : & ModInt < M >) { self .$ op_assign (* rhs) ; } }) * } ; }
    op_impl! { Add add AddAssign add_assign Sub sub SubAssign sub_assign Mul mul MulAssign mul_assign Div div DivAssign div_assign }
    impl<M: Modulo> std::iter::Sum for ModInt<M> {
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(ModInt::new(0), |x, y| x + y)
        }
    }
    impl<M: Modulo> std::iter::Product for ModInt<M> {
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(ModInt::new(1), |x, y| x * y)
        }
    }
    pub trait Pow<T> {
        fn pow(self, n: T) -> Self;
    }
    impl<M: Modulo> Pow<u32> for ModInt<M> {
        fn pow(mut self, mut n: u32) -> Self {
            let mut y = Self::new(1);
            while n > 0 {
                if n % 2 == 1 {
                    y *= self;
                }
                self *= self;
                n /= 2;
            }
            y
        }
    }
    macro_rules ! mod_int_pow_impl { ($ ($ T : ident) *) => { $ (impl < M : Modulo > Pow <$ T > for ModInt < M > { fn pow (self , n : $ T) -> Self { self . pow (n . rem_euclid (M :: modulo () as $ T - 1) as u32) } }) * } ; }
    mod_int_pow_impl ! (isize i32 i64 usize u64);
    macro_rules ! mod_int_from_impl { ($ ($ T : ident) *) => { $ (impl < M : Modulo > From <$ T > for ModInt < M > { # [allow (unused_comparisons)] fn from (x : $ T) -> Self { if M :: modulo () <= $ T :: max_value () as u32 { Self :: new (x . rem_euclid (M :: modulo () as $ T) as u32) } else if x < 0 { Self :: new ((M :: modulo () as i32 + x as i32) as u32) } else { Self :: new (x as u32) } } }) * } }
    mod_int_from_impl ! (isize i8 i16 i32 i64 i128 usize u8 u16 u32 u64 u128);
    impl<M: Modulo> From<bool> for ModInt<M> {
        fn from(x: bool) -> Self {
            Self::new(x as u32)
        }
    }
    impl<M> Copy for ModInt<M> {}
    impl<M> Clone for ModInt<M> {
        fn clone(&self) -> Self {
            *self
        }
    }
    impl<M: Modulo> Default for ModInt<M> {
        fn default() -> Self {
            Self::new(0)
        }
    }
    impl<M> cmp::PartialEq for ModInt<M> {
        fn eq(&self, other: &Self) -> bool {
            self.0 == other.0
        }
    }
    impl<M> cmp::Eq for ModInt<M> {}
    impl<M> cmp::PartialOrd for ModInt<M> {
        fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
            self.0.partial_cmp(&other.0)
        }
    }
    impl<M> cmp::Ord for ModInt<M> {
        fn cmp(&self, other: &Self) -> cmp::Ordering {
            self.0.cmp(&other.0)
        }
    }
    impl<M> std::hash::Hash for ModInt<M> {
        fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
            self.0.hash(state);
        }
    }
    impl<M> fmt::Display for ModInt<M> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            self.0.fmt(f)
        }
    }
    impl<M> fmt::Debug for ModInt<M> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            self.0.fmt(f)
        }
    }
}
pub mod macros {
    #[macro_export]
    macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }
    #[macro_export]
    macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
    #[macro_export]
    macro_rules! w_iter {
        ($dst:expr, $fmt:expr, $iter:expr, $delim:expr) => {{
            let mut first = true;
            for elem in $iter {
                if first {
                    w!($dst, $fmt, elem);
                    first = false;
                } else {
                    w!($dst, concat!($delim, $fmt), elem);
                }
            }
        }};
        ($dst:expr, $fmt:expr, $iter:expr) => {
            w_iter!($dst, $fmt, $iter, " ")
        };
    }
    #[macro_export]
    macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
    #[macro_export]
    macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
    #[macro_export]
    macro_rules ! d { ($ ($ a : expr) ,*) => { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) } ; }
}
pub mod pio2 {
    use std::{
        io::prelude::*,
        marker::PhantomData,
        mem::{self, MaybeUninit},
        str,
    };
    pub trait Input {
        fn bytes(&mut self) -> &[u8];
        fn str(&mut self) -> &str {
            str::from_utf8(self.bytes()).unwrap()
        }
        fn parse<T>(&mut self) -> T
        where
            DefaultParser: Parser<T>,
        {
            self.parse_with(DefaultParser)
        }
        fn parse_with<T, P: Parser<T>>(&mut self, mut parser: P) -> T {
            parser.parse(self)
        }
        fn seq<T>(&mut self, n: usize) -> Seq<Self, T, DefaultParser>
        where
            DefaultParser: Parser<T>,
        {
            self.seq_with(n, DefaultParser)
        }
        fn seq_with<T, P: Parser<T>>(&mut self, n: usize, parser: P) -> Seq<Self, T, P> {
            Seq {
                src: self,
                rest: n,
                parser,
                phantom: PhantomData,
            }
        }
    }
    impl<I: Input> Input for &mut I {
        fn bytes(&mut self) -> &[u8] {
            (**self).bytes()
        }
    }
    pub struct Scanner<R> {
        src: R,
        buf: Vec<u8>,
        pos: usize,
        len: usize,
    }
    impl<R: Read> Scanner<R> {
        pub fn new(src: R) -> Self {
            Self {
                src,
                buf: vec![0; 1 << 16],
                pos: 0,
                len: 0,
            }
        }
        fn read(&mut self) -> usize {
            if self.pos > 0 {
                self.buf.copy_within(self.pos..self.len, 0);
                self.len -= self.pos;
                self.pos = 0;
            } else if self.len >= self.buf.len() {
                self.buf.resize(2 * self.buf.len(), 0);
            }
            let n = self.src.read(&mut self.buf[self.len..]).unwrap();
            self.len += n;
            assert!(self.len <= self.buf.len());
            n
        }
    }
    impl<R: Read> Input for Scanner<R> {
        fn bytes(&mut self) -> &[u8] {
            loop {
                while let Some(d) = unsafe { self.buf.get_unchecked(self.pos..self.len) }
                    .iter()
                    .position(u8::is_ascii_whitespace)
                {
                    let p = self.pos;
                    self.pos += d + 1;
                    if d > 0 {
                        return unsafe { self.buf.get_unchecked(p..p + d) };
                    }
                }
                if self.read() == 0 {
                    let p = self.pos;
                    if p == self.len {
                        panic!("reached EOF");
                    }
                    self.pos = self.len;
                    return unsafe { self.buf.get_unchecked(p..self.len) };
                }
            }
        }
    }
    pub struct Seq<'a, I: ?Sized, T, P> {
        src: &'a mut I,
        rest: usize,
        parser: P,
        phantom: PhantomData<*const T>,
    }
    impl<'a, I: Input + ?Sized, T, P: Parser<T>> Iterator for Seq<'a, I, T, P> {
        type Item = T;
        fn next(&mut self) -> Option<T> {
            if self.rest > 0 {
                self.rest -= 1;
                Some(self.src.parse_with(&mut self.parser))
            } else {
                None
            }
        }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rest, Some(self.rest))
        }
    }
    impl<'a, I: Input + ?Sized, T, P: Parser<T>> ExactSizeIterator for Seq<'a, I, T, P> {}
    pub trait Parser<T> {
        fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T;
    }
    impl<T, P: Parser<T>> Parser<T> for &mut P {
        fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T {
            (*self).parse(src)
        }
    }
    #[derive(Clone, Copy, Debug)]
    pub struct DefaultParser;
    macro_rules! int {
        ($ty:ident) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty);
                    let s = src.bytes();
                    if let Some((&b'-', t)) = s.split_first() {
                        -f(t)
                    } else {
                        f(s)
                    }
                }
            }
        };
    }
    int!(isize);
    int!(i8);
    int!(i16);
    int!(i32);
    int!(i64);
    int!(i128);
    macro_rules! uint {
        ($ty:ident) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty)
                }
            }
        };
    }
    uint!(usize);
    uint!(u8);
    uint!(u16);
    uint!(u32);
    uint!(u64);
    uint!(u128);
    macro_rules! from_bytes {
        ($ty:ty) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.bytes().into()
                }
            }
        };
    }
    from_bytes!(Vec<u8>);
    from_bytes!(Box<[u8]>);
    macro_rules! from_str {
        ($ty:ident) => {
            impl Parser<$ty> for DefaultParser {
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.str().parse::<$ty>().expect("failed to parse")
                }
            }
        };
    }
    from_str!(String);
    from_str!(char);
    from_str!(f32);
    from_str!(f64);
    macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T) ,+> Parser < ($ ($ T ,) +) > for DefaultParser where $ (DefaultParser : Parser <$ T >) ,+ { fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> ($ ($ T ,) +) { ($ (< Self as Parser <$ T >>:: parse (self , src) ,) +) } } } ; }
    tuple!(A);
    tuple!(A, B);
    tuple!(A, B, C);
    tuple!(A, B, C, D);
    tuple!(A, B, C, D, E);
    tuple!(A, B, C, D, E, F);
    tuple!(A, B, C, D, E, F, G);
    tuple!(A, B, C, D, E, F, G, H);
    macro_rules ! array { ($ ($ N : literal) *) => { $ (impl < T > Parser < [T ; $ N] > for DefaultParser where DefaultParser : Parser < T > { fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> [T ; $ N] { unsafe { let mut arr : [MaybeUninit < T >; $ N] = MaybeUninit :: uninit () . assume_init () ; for elem in & mut arr { * elem = MaybeUninit :: new (src . parse ()) ; } mem :: transmute_copy (& arr) } } }) * } }
    array ! (1 2 3 4 5 6 7 8);
}
yukicoder

結果

テストケース

ソースコード
