#385109 (Rust) No.891 隣接3項間の漸化式

提出ソース

結果

問題	No.891 隣接3項間の漸化式
ユーザー	wesrivery
提出日時	2019-09-28 16:34:57
言語	Rust (1.77.0)
結果	AC
実行時間	1 ms / 2,000 ms
コード長	7,584 bytes
コンパイル時間	1,411 ms
コンパイル使用メモリ	182,124 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-10 09:03:56
合計ジャッジ時間	2,733 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	1 ms 6,940 KB
testcase_09	AC	1 ms 6,944 KB
testcase_10	AC	1 ms 6,944 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	1 ms 6,940 KB
testcase_13	AC	1 ms 6,944 KB
testcase_14	AC	1 ms 6,940 KB
testcase_15	AC	0 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,944 KB
testcase_20	AC	1 ms 6,944 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	AC	1 ms 6,944 KB
testcase_23	AC	1 ms 6,940 KB
testcase_24	AC	1 ms 6,940 KB
testcase_25	AC	1 ms 6,944 KB
testcase_26	AC	1 ms 6,940 KB
testcase_27	AC	1 ms 6,940 KB
testcase_28	AC	1 ms 6,940 KB
testcase_29	AC	1 ms 6,944 KB
testcase_30	AC	1 ms 6,944 KB
testcase_31	AC	1 ms 6,944 KB
testcase_32	AC	1 ms 6,940 KB
testcase_33	AC	1 ms 6,940 KB
testcase_34	AC	0 ms 6,940 KB
testcase_35	AC	1 ms 6,940 KB
testcase_36	AC	1 ms 6,940 KB
testcase_37	AC	1 ms 6,940 KB
testcase_38	AC	1 ms 6,940 KB
testcase_39	AC	1 ms 6,944 KB
testcase_40	AC	1 ms 6,940 KB
testcase_41	AC	1 ms 6,940 KB

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

ソースコード

raw source code

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*)
    }}
}


#[allow(dead_code)]
mod mat {
    use std::fmt::{Debug, Display, Formatter, Result};
    use std::iter::Sum;
    use std::ops::Add;
    use std::ops::Index;
    use std::ops::Mul;
    #[derive(Eq, Clone)]
    pub struct Mat<T: PartialEq + Eq + Debug + Display> {
        inside_vec: Vec<Vec<T>>,
        pub row: usize,
        pub col: usize,
    }
    impl<T: PartialEq + Eq + Debug + Display> Index<usize> for Mat<T> {
        type Output = Vec<T>;
        fn index(&self, i: usize) -> &Self::Output {
            &self.inside_vec[i]
        }
    }
    impl<T: PartialEq + Eq + Debug + Display> Mat<T> {
        pub fn new(v: Vec<Vec<T>>) -> Self {
            if let Some((row, col)) = Mat::row_col(&v) {
                Mat {
                    inside_vec: v,
                    row: row,
                    col: col,
                }
            } else {
                panic!("passed vector's length is not valid.");
            }
        }
        pub fn from_vec(v: Vec<T>) -> Self {
            let col = v.len();
            Mat {
                inside_vec: vec![v],
                row: 1,
                col: col,
            }
        }
        fn row_col(v: &Vec<Vec<T>>) -> Option<(usize, usize)> {
            let col = v[0].len();
            for line in v.iter() {
                if line.len() != col {
                    return None;
                }
            }
            return Some((v.len(), col));
        }
    }
    impl<T: Copy + PartialEq + Eq + Debug + Display> Mat<T> {
        pub fn transpose(self) -> Self {
            let row = self.col;
            let col = self.row;
            let mut inside: Vec<Vec<T>> = Vec::with_capacity(row);
            for i in 0..row {
                let cols = (0..col).map(|k| self[k][i]);
                inside.push(cols.collect());
            }
            Mat {
                inside_vec: inside,
                row: row,
                col: col,
            }
        }
    }
    impl<T: PartialEq + Eq + Debug + Display> PartialEq for Mat<T> {
        fn eq(&self, other: &Self) -> bool {
            if self.row == other.row && self.col == other.col {
                for row in 0..self.row {
                    for col in 0..self.col {
                        if self[row][col] != other[row][col] {
                            return false;
                        }
                    }
                }
                return true;
            }
            return false;
        }
    }
    impl<T: PartialEq + Eq + Debug + Display> Debug for Mat<T> {
        fn fmt(&self, f: &mut Formatter) -> Result {
            let mut s = "".to_string();
            for line in &self.inside_vec {
                s += "|";
                for val in line {
                    s += &format!(" {:^3}", val);
                }
                s += " |\n";
            }
            write!(f, "{}", s)
        }
    }
    impl<T: PartialEq + Eq + Debug + Display> Display for Mat<T> {
        fn fmt(&self, f: &mut Formatter) -> Result {
            let mut s = "".to_string();
            for line in &self.inside_vec {
                s += "|";
                for val in line {
                    s += &format!(" {:^3}", val);
                }
                s += " |\n";
            }
            write!(f, "{}", s)
        }
    }
    impl<T> Mul for Mat<T>
    where
        T: Mul<Output = T> + Add + Sum + Copy + PartialEq + Eq + Debug + Display,
    {
        type Output = Self;
        fn mul(self, rhs: Self) -> Self {
            if self.col != rhs.row {
                panic ! ( "length of column of left hand side doesn't equal to length of row of right hand side." );
            }
            let mut product: Vec<Vec<T>> = Vec::with_capacity(rhs.row);
            for _ in 0..rhs.row {
                product.push(Vec::<T>::with_capacity(self.col));
            }
            for i in 0..self.row {
                for j in 0..rhs.col {
                    let row = self[i].iter();
                    let col = (0..rhs.row).map(|k| rhs[k][j]);
                    product[i].push(row.zip(col).map(|(s, r)| *s * r).sum());
                }
            }
            Mat::new(product)
        }
    }
    impl<T> Mul for &'_ Mat<T>
    where
        T: Mul<Output = T> + Add + Sum + Copy + PartialEq + Eq + Debug + Display,
    {
        type Output = Mat<T>;
        fn mul(self, rhs: Self) -> Mat<T> {
            if self.col != rhs.row {
                panic ! ( "length of column of left hand side doesn't equal to length of row of right hand side." );
            }
            let mut product: Vec<Vec<T>> = Vec::with_capacity(rhs.row);
            for _ in 0..rhs.row {
                product.push(Vec::<T>::with_capacity(self.col));
            }
            for i in 0..self.row {
                for j in 0..rhs.col {
                    let row = self[i].iter();
                    let col = (0..rhs.row).map(|k| rhs[k][j]);
                    product[i].push(row.zip(col).map(|(s, r)| *s * r).sum());
                }
            }
            Mat::new(product)
        }
    }
    impl<T> Add for Mat<T>
    where
        T: Add<Output = T> + Copy + PartialEq + Eq + Debug + Display,
    {
        type Output = Self;
        fn add(self, rhs: Self) -> Self {
            if self.row != rhs.row {
                panic!("length of row is not currespond.");
            }
            if self.col != rhs.col {
                panic!("length of column is not currespond.");
            }
            let mut sum: Vec<Vec<T>> = Vec::with_capacity(self.row);
            for _ in 0..self.row {
                sum.push(Vec::<T>::with_capacity(self.col));
            }
            for i in 0..self.row {
                for j in 0..self.col {
                    sum[i].push(self[i][j] + rhs[i][j]);
                }
            }
            Mat::new(sum)
        }
    }
    impl<T> Mat<T>
    where
        T: Add + Mul<Output = T> + Sum + Copy + PartialEq + Eq + Debug + Display,
    {
        pub fn pow<F: Fn(T) -> T + Copy>(self, n: u32, f: F) -> Self {
            let mut current = self.clone();
            let base = self.clone();
            for b in format!("{:b}", n).chars().skip(1) {
                current = (current.clone() * current).map(f);
                match b {
                    '1' => current = (base.clone() * current.clone()).map(f),
                    _ => (),
                }
            }
            current
        }
        pub fn map<F>(self, f: F) -> Mat<T>
        where
            F: Fn(T) -> T,
        {
            let mut newvec = Vec::with_capacity(self.row);
            for row in 0..self.row {
                newvec.push(Vec::with_capacity(self.col));
                for col in 0..self.col {
                    newvec[row].push(f(self.inside_vec[row][col]));
                }
            }
            Mat::new(newvec)
        }
    }
}

const MOD: u64 = 1_000_000_007;

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    use mat::Mat;
    let (a, b, n) = input!(u64, u64, u32);

    if n == 0 {
        println!("0");
        return;
    }

    let m = Mat::new(vec![vec![a, b],
                          vec![1, 0]]);
    println!("{}", m.pow(n, |x| x % MOD)[1][0]);
}

fn main() {
    solve();
}

yukicoder

結果

テストケース

ソースコード