#731293 (Rust) No.1810 RGB Biscuits

提出ソース

結果

問題	No.1810 RGB Biscuits
ユーザー	Strorkis
提出日時	2022-01-15 18:31:40
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	49 ms / 2,000 ms
コード長	11,677 bytes
コンパイル時間	15,604 ms
コンパイル使用メモリ	379,800 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-21 21:31:13
合計ジャッジ時間	16,673 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	44 ms 5,248 KB
testcase_06	AC	48 ms 5,248 KB
testcase_07	AC	48 ms 5,248 KB
testcase_08	AC	49 ms 5,248 KB
testcase_09	AC	49 ms 5,248 KB
testcase_10	AC	30 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	8 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	4 ms 5,248 KB
testcase_17	AC	23 ms 5,248 KB
testcase_18	AC	24 ms 5,248 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	6 ms 5,248 KB

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

ソースコード

raw source code

pub mod input {
    pub trait Readable {
        type Output;

        fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output;
    }

    macro_rules! impl_readable_for_int {
        ($($t:ty)*) => ($(impl Readable for $t {
            type Output = $t;

            #[inline]
            fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
                let mut is_positive = true;
                let mut is_empty = true;
                let mut is_only_sign = true;
                let mut result: Self::Output = 0;
                loop {
                    let buf = match r.fill_buf() {
                        Ok(buf) => buf,
                        Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue,
                        Err(e) => panic!("{}", e), 
                    };
                    let (done, used, mut buf) = match buf.iter().position(u8::is_ascii_whitespace) {
                        Some(i) => (i > 0 || !is_empty, i + 1, &buf[..i]),
                        None => (buf.is_empty(), buf.len(), buf),
                    };
        
                    if is_empty && buf.len() > 0 {
                        is_empty = false;
                        buf = match buf[0] {
                            b'+' => &buf[1..],
                            b'-' => {
                                is_positive = false;
                                &buf[1..]
                            }
                            _ => buf,
                        };
                    }
                    if buf.len() > 0 {
                        is_only_sign = false;
                    }
        
                    if is_positive {
                        for &c in buf {
                            let x = (c as char).to_digit(10).expect("InvalidDigit");
                            result = result.checked_mul(10).expect("PosOverflow");
                            result = result.checked_add(x as $t).expect("PosOverflow");
                        }
                    } else {
                        for &c in buf {
                            let x = (c as char).to_digit(10).expect("InvalidDigit");
                            result = result.checked_mul(10).expect("NegOverflow");
                            result = result.checked_sub(x as $t).expect("NegOverflow");
                        }
                    }
        
                    r.consume(used);
        
                    if done {
                        if is_empty {
                            panic!("Empty");
                        }
                        if is_only_sign {
                            panic!("InvalidDigit");
                        }        
                        return result;
                    }
                }
            }
        })*)
    }
    impl_readable_for_int! { i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize }

    pub mod marker {
        use super::Readable;
        
        pub enum Usize1 {}

        impl Readable for Usize1 {
            type Output = usize;

            #[inline]
            fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
                usize::read(r).checked_sub(1).expect("NegOverflow")
            }
        }

        pub enum Bytes {}

        impl Readable for Bytes {
            type Output = Vec<u8>;

            #[inline]
            fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
                let mut result = Vec::new();
                loop {
                    let buf = match r.fill_buf() {
                        Ok(buf) => buf,
                        Err(e) if e.kind() == std::io::ErrorKind::Interrupted => continue,
                        Err(e) => panic!("{}", e), 
                    };
                    let (done, used, buf) = match buf.iter().position(u8::is_ascii_whitespace) {
                        Some(i) => (i > 0 || !result.is_empty(), i + 1, &buf[..i]),
                        None => (buf.is_empty(), buf.len(), buf),
                    };
                    result.extend_from_slice(buf);
                    r.consume(used);
                    if done { return result; }
                }
            }
        }
    }

    impl Readable for String {
        type Output = String;

        #[inline]
        fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
            String::from_utf8(marker::Bytes::read(r)).unwrap()
        }
    }

    macro_rules! impl_readable_for_float {
        ($($t:ty)*) => ($(impl Readable for $t {
            type Output = $t;
            
            #[inline]
            fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {
                String::read(r).parse().unwrap()
            }
        })*)
    }
    impl_readable_for_float! { f32 f64 }

    macro_rules! impl_readable_for_tuple {
        ($head:ident, $($tail:ident),*) => {
            impl<$head, $($tail),*> Readable for ($head, $($tail),*)
            where
                $head: Readable,
                $($tail: Readable),*,
            {
                type Output = (
                    <$head as Readable>::Output,
                    $(<$tail as Readable>::Output),*,
                );

                #[inline]
                fn read<R: std::io::BufRead>(r: &mut R) -> Self::Output {    
                    (<$head>::read(r), $(<$tail>::read(r)),*)
                }
            }
            impl_readable_for_tuple!($($tail),*);
        };
        ($head:ident) => {};
    }
    impl_readable_for_tuple!(A, B, C, D, E, F, G, H, I, J);

    #[macro_export]
    macro_rules! read {
        ($r:expr, [$t:tt; $n:expr]) => {{
            <[_; $n]>::try_from(read!($r, ($t; $n)).as_slice()).unwrap()
        }};
        ($r:expr, ($t:tt)) => {
            read!($r, ($t; read!($r, usize)))
        };
        ($r:expr, ($t:tt; $n:expr)) => {
            (0..$n).map(|_| read!($r, $t)).collect::<Vec<_>>()
        };
        ($r:expr, $t:ty) => {
            <$t>::read($r)
        };
    }

    #[macro_export]
    macro_rules! input {
        ($r:expr, $($($v:ident)* : $t:tt),* $(,)?) => {$(
            let $($v)* = read!($r, $t);
        )*};
    }
}

pub mod matrix {
    use std::ops::{Add, Mul};

    pub trait MatrixHelper: Add<Output = Self> + Mul<Output = Self> + Copy {
        fn zero() -> Self;
        fn one() -> Self;
    }
    
    #[derive(Clone, Debug)]
    pub struct Matrix<M> {
        n: usize, m: usize, a: Vec<Vec<M>>,
    }

    impl<M: MatrixHelper> Matrix<M> {
        pub fn new(n: usize, m: usize, a: Vec<Vec<M>>) -> Self {
            Matrix {
                n, m, a
            }
        }

        pub fn zero(n: usize, m: usize) -> Self {
            Matrix::new(n, m, vec![vec![M::zero(); m]; n])
        }

        pub fn identity(n: usize) -> Self {
            let mut res = Matrix::zero(n, n);
            for i in 0..n {
                res.a[i][i] = M::one();
            }
            res
        }

        pub fn get(&self, i: usize, j: usize) -> &M {
            &self.a[i][j]
        }

        pub fn set(&mut self, i: usize, j: usize, m: M) {
            self.a[i][j] = m;
        }

        pub fn mul(&self, other: &Self) -> Self {
            assert!(self.m == other.n);
            let mut res = Matrix::zero(self.n, other.m);
            for (res, b) in res.a.iter_mut().zip(self.a.iter()) {
                for (&b, c) in b.iter().zip(other.a.iter()) {
                    for (res, &c) in res.iter_mut().zip(c.iter()) {
                        *res = *res + b * c;
                    }
                }
            }
            res
        }

        pub fn pow(&self, mut n: u64) -> Self {
            assert!(self.n == self.m);
            let mut res = Matrix::identity(self.n);
            let mut x = self.clone();
            while n > 0 {
                if n & 1 == 1 {
                    res = res.mul(&x);
                }
                x = x.mul(&x);
                n >>= 1;
            }
            res
        }
    }
}

pub mod mod_int {
    use std::fmt;
    use std::ops::*;

    #[derive(Clone, Copy, Debug, Default)]
    pub struct ModInt(u64);

    impl ModInt {
        const MOD: u64 = 1_000_000_007;

        pub fn new(mut x: u64) -> Self {
            if x >= Self::MOD {
                x %= Self::MOD;
            }
            Self(x)
        }

        pub fn zero() -> Self {
            Self(0)
        }

        pub fn one() -> Self {
            Self(1)
        }
    }

    impl From<usize> for ModInt {
        fn from(x: usize) -> Self {
            Self::new(x as u64)
        }
    }

    impl From<i64> for ModInt {
        fn from(mut x: i64) -> Self {
            let m = Self::MOD as i64;
            if x.abs() >= m {
                x %= m;
            }
            if x < 0 {
                x += m
            }
            Self::new(x as u64)
        }
    }

    impl Add for ModInt {
        type Output = Self;

        fn add(self, other: Self) -> Self {
            let mut x = self.0 + other.0;
            if x >= Self::MOD {
                x -= Self::MOD;
            }
            Self(x)
        }
    }

    impl AddAssign for ModInt {
        fn add_assign(&mut self, other: Self) {
            *self = *self + other;
        }
    }

    impl Sub for ModInt {
        type Output = Self;

        fn sub(mut self, other: Self) -> Self {
            if self.0 < other.0 {
                self.0 += Self::MOD;
            }
            Self(self.0 - other.0)
        }
    }

    impl SubAssign for ModInt {
        fn sub_assign(&mut self, other: Self) {
            *self = *self - other;
        }
    }

    impl Mul for ModInt {
        type Output = Self;

        fn mul(self, other: Self) -> Self {
            Self::new(self.0 * other.0)
        }
    }

    impl MulAssign for ModInt {
        fn mul_assign(&mut self, other: Self) {
            *self = *self * other;
        }
    }

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

    impl ModInt {
        pub fn pow(mut self, mut n: u64) -> Self {
            let mut res = Self::one();
            while n > 0 {
                if n & 1 == 1 {
                    res *= self;
                }
                self *= self;
                n >>= 1;
            }
            res
        }
        
        pub fn inv(self) -> Self {
            self.pow(Self::MOD - 2)
        }
    }
}

use input::Readable;
use matrix::{Matrix, MatrixHelper};
use mod_int::ModInt;

impl MatrixHelper for ModInt {
    fn zero() -> Self {
        Self::zero()
    }
    fn one() -> Self {
        Self::one()
    }
}

fn run<R: std::io::BufRead, W: std::io::Write>(reader: &mut R, writer: &mut W) {
    input! {
        reader,
        a: u64, b: u64,
    }

    let mut m0 = Matrix::zero(6, 1);
    m0.set(0, 0, ModInt::one());
    m0.set(1, 0, ModInt::one());

    let mut m = Matrix::zero(6, 6);
    m.set(3, 0, ModInt::one());
    m.set(4, 1, ModInt::one());
    m.set(5, 0, ModInt::new(a));
    m.set(5, 1, ModInt::new(b));
    m.set(1, 3, ModInt::one());
    m.set(0, 5, ModInt::one());

    for _ in 0..read!(reader, usize) {
        let t = read!(reader, u64);

        let res = m.pow(t).mul(&m0);
        let mut ans = ModInt::zero();
        for i in 0..6 {
            ans += *res.get(i, 0);
        }
        writeln!(writer, "{}", ans).ok();
    }
}

fn main() {
    let (stdin, stdout) = (std::io::stdin(), std::io::stdout());
    let ref mut reader = std::io::BufReader::new(stdin.lock());
    let ref mut writer = std::io::BufWriter::new(stdout.lock());
    run(reader, writer);
}

yukicoder

結果

テストケース

ソースコード