#682032 (Rust) No.1620 Substring Sum

提出ソース

結果

問題	No.1620 Substring Sum
ユーザー	Rheo Tommy
提出日時	2021-07-22 22:52:25
言語	Rust (1.77.0)
結果	AC
実行時間	50 ms / 2,000 ms
コード長	9,346 bytes
コンパイル時間	2,533 ms
コンパイル使用メモリ	154,120 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-24 18:32:37
合計ジャッジ時間	4,442 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,384 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	50 ms 4,376 KB
testcase_05	AC	49 ms 4,376 KB
testcase_06	AC	50 ms 4,380 KB
testcase_07	AC	49 ms 4,380 KB
testcase_08	AC	49 ms 4,376 KB
testcase_09	AC	47 ms 4,380 KB
testcase_10	AC	48 ms 4,380 KB
testcase_11	AC	48 ms 4,380 KB
testcase_12	AC	15 ms 4,376 KB
testcase_13	AC	45 ms 4,376 KB
testcase_14	AC	46 ms 4,376 KB
testcase_15	AC	40 ms 4,380 KB
testcase_16	AC	28 ms 4,380 KB
testcase_17	AC	38 ms 4,376 KB
testcase_18	AC	1 ms 4,376 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	48 ms 4,380 KB
testcase_21	AC	49 ms 4,380 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

// # ファイル構成
// - use 宣言
// - lib モジュール
// - main 関数
// - basic モジュール
//
// 常に使うテンプレートライブラリは basic モジュール内にあります。
// 問題に応じて使うライブラリ lib モジュール内にコピペしています。
// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder
// Twitter はこちら → https://twitter.com/RheoTommy

use std::collections::*;
use std::io::{stdout, BufWriter, Write};

use crate::basic::*;
use crate::lib::*;

pub mod lib {
    pub type ModInt = StaticModInt;

    pub const MOD: i32 = MOD998244353;
    pub const MOD1000000007: i32 = 1000000007;
    pub const MOD998244353: i32 = 998244353;

    #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
    pub struct StaticModInt(i32);

    impl std::fmt::Display for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self.0)
        }
    }

    impl std::fmt::Debug for StaticModInt {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            write!(f, "{}", self)
        }
    }

    impl StaticModInt {
        pub fn new<T: Into<StaticModInt>>(n: T) -> Self {
            n.into()
        }
        fn new_inner(n: i32) -> Self {
            Self(n)
        }
        pub fn pow<T: Into<Int>>(self, n: T) -> Self {
            let n: Int = n.into();
            let mut n = n.0;
            assert!(n >= 0);
            let mut res = StaticModInt::new(1);
            let mut x = self;
            while n != 0 {
                if n & 1 == 1 {
                    res *= x;
                }
                n /= 2;
                x *= x;
            }
            res
        }
        pub fn inv(self) -> Self {
            self.pow((MOD - 2) as u64)
        }
    }

    impl<T: Into<Int>> From<T> for StaticModInt {
        fn from(t: T) -> Self {
            let n: Int = t.into();
            let n = (n.0 % MOD as i64) as i32;
            if n < 0 {
                Self::new_inner(n + MOD)
            } else {
                Self::new_inner(n)
            }
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Add<T> for StaticModInt {
        type Output = Self;
        fn add(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp += t.0;
            if tmp >= MOD {
                tmp -= MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::AddAssign<T> for StaticModInt {
        fn add_assign(&mut self, rhs: T) {
            *self = *self + rhs.into()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Sub<T> for StaticModInt {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut tmp = self.0;
            let t: StaticModInt = rhs.into();
            tmp -= t.0;
            if tmp < 0 {
                tmp += MOD;
            }
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::SubAssign<T> for StaticModInt {
        fn sub_assign(&mut self, rhs: T) {
            *self = *self - rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Mul<T> for StaticModInt {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut tmp = self.0 as i64;
            let t: StaticModInt = rhs.into();
            tmp *= t.0 as i64;
            if tmp >= MOD as i64 {
                tmp %= MOD as i64;
            }
            let tmp = tmp as i32;
            debug_assert!((0..MOD).contains(&tmp));
            Self(tmp)
        }
    }

    impl<T: Into<StaticModInt>> std::ops::MulAssign<T> for StaticModInt {
        fn mul_assign(&mut self, rhs: T) {
            *self = *self * rhs.into();
        }
    }

    impl<T: Into<StaticModInt>> std::ops::Div<T> for StaticModInt {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let t: StaticModInt = rhs.into();
            self * t.inv()
        }
    }

    impl<T: Into<StaticModInt>> std::ops::DivAssign<T> for StaticModInt {
        fn div_assign(&mut self, rhs: T) {
            *self = *self / rhs.into();
        }
    }

    /// 二項係数を高速に計算するテーブルを作成する
    /// 構築 O(N)
    /// クエリ O(1)
    /// メモリ O(N)
    pub struct CombTable {
        fac: Vec<ModInt>,
        f_inv: Vec<ModInt>,
    }

    impl CombTable {
        /// O(N)で構築
        pub fn new<T: Into<Int>>(n: T) -> Self {
            let n: Int = n.into();
            assert!(n.0 >= 0);
            let n = n.0 as usize;
            let mut fac = vec![ModInt::new(1); n + 1];
            let mut f_inv = vec![ModInt::new(1); n + 1];
            let mut inv = vec![ModInt::new(1); n + 1];
            inv[0] = ModInt::new(0);
            for i in 2..=n {
                fac[i] = fac[i - 1] * i;
                inv[i] =
                    ModInt::new(MOD) - inv[(MOD % i as i32) as usize] * ModInt::new(MOD / i as i32);
                f_inv[i] = f_inv[i - 1] * inv[i];
            }
            Self { fac, f_inv }
        }
        /// nCkをO(1)で計算
        pub fn comb<T1: Into<Int>, T2: Into<Int>>(&self, n: T1, k: T2) -> ModInt {
            let n: Int = n.into();
            let k: Int = k.into();
            assert!(n.0 >= 0);
            assert!(k.0 >= 0);
            let n = n.0 as usize;
            let k = k.0 as usize;
            if n < k {
                return ModInt::new(0);
            }
            self.fac[n] * (self.f_inv[k] * self.f_inv[n - k])
        }
    }

    #[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)]
    pub struct Int(pub i64);
    macro_rules! impl_int_from {($ ($ t : ty ) ,* ) => {$ (impl From < Int > for $ t {fn from (t : Int ) -> $ t {t . 0 as $ t } } ) * } ; }
    impl_int_from!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
    macro_rules! impl_int_into {($ ($ t : ty ) ,* ) => {$ (impl Into < Int > for $ t {fn into (self ) -> Int {Int (self as i64 ) } } ) * } ; }
    impl_int_into!(i8, i16, i32, i64, u8, u16, u32, u64, isize, usize);
}

fn main() {
    let mut io = IO::new();
    let s = io.next_chars().map(|ci| ModInt::new(ci.to_digit(10).unwrap())).collect::<Vec<_>>();

    let mut sum = ModInt::new(0);
    let n = s.len();
    for i in 0..n {
        sum += ModInt::new(2).pow(i) * ModInt::new(11).pow(n - i - 1) * s[i];
    }
    io.println(sum);
}

pub mod basic {
    pub const U_INF: u64 = (1 << 60) + (1 << 30);
    pub const I_INF: i64 = (1 << 60) + (1 << 30);
    pub const INF: usize = (1 << 60) + (1 << 30);

    pub struct IO {
        iter: std::str::SplitAsciiWhitespace<'static>,
        buf: std::io::BufWriter<std::io::StdoutLock<'static>>,
    }

    impl Default for IO {
        fn default() -> Self {
            Self::new()
        }
    }

    impl IO {
        pub fn new() -> Self {
            use std::io::*;
            let mut input = String::new();
            std::io::stdin().read_to_string(&mut input).unwrap();
            let input = Box::leak(input.into_boxed_str());
            let out = Box::new(stdout());
            IO {
                iter: input.split_ascii_whitespace(),
                buf: BufWriter::new(Box::leak(out).lock()),
            }
        }
        pub fn next_str(&mut self) -> &str {
            self.iter.next().unwrap()
        }
        pub fn read<T: std::str::FromStr>(&mut self) -> T
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            self.iter.next().unwrap().parse().unwrap()
        }
        pub fn next_usize(&mut self) -> usize {
            self.read()
        }
        pub fn next_uint(&mut self) -> u64 {
            self.read()
        }
        pub fn next_int(&mut self) -> i64 {
            self.read()
        }
        pub fn next_float(&mut self) -> f64 {
            self.read()
        }
        pub fn next_chars(&mut self) -> std::str::Chars {
            self.next_str().chars()
        }
        pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T>
            where
                <T as std::str::FromStr>::Err: std::fmt::Debug,
        {
            (0..n).map(|_| self.read()).collect::<Vec<_>>()
        }
        pub fn print<T: std::fmt::Display>(&mut self, t: T) {
            use std::io::Write;
            write!(self.buf, "{}", t).unwrap();
        }
        pub fn println<T: std::fmt::Display>(&mut self, t: T) {
            self.print(t);
            self.print("\n");
        }
        pub fn print_iter<T: std::fmt::Display, I: Iterator<Item=T>>(
            &mut self,
            mut iter: I,
            sep: &str,
        ) {
            if let Some(v) = iter.next() {
                self.print(v);
                for vi in iter {
                    self.print(sep);
                    self.print(vi);
                }
            }
            self.print("\n");
        }
        pub fn flush(&mut self) {
            use std::io::Write;
            self.buf.flush().unwrap();
        }
    }
}

yukicoder

結果

テストケース

ソースコード