結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー | wesrivery |
提出日時 | 2019-09-28 16:34:57 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 7,584 bytes |
コンパイル時間 | 13,143 ms |
コンパイル使用メモリ | 375,140 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-02 10:50:16 |
合計ジャッジ時間 | 14,610 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 0 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 1 ms
5,248 KB |
testcase_12 | AC | 1 ms
5,248 KB |
testcase_13 | AC | 1 ms
5,248 KB |
testcase_14 | AC | 1 ms
5,248 KB |
testcase_15 | AC | 1 ms
5,248 KB |
testcase_16 | AC | 1 ms
5,248 KB |
testcase_17 | AC | 1 ms
5,248 KB |
testcase_18 | AC | 1 ms
5,248 KB |
testcase_19 | AC | 1 ms
5,248 KB |
testcase_20 | AC | 1 ms
5,248 KB |
testcase_21 | AC | 1 ms
5,248 KB |
testcase_22 | AC | 1 ms
5,248 KB |
testcase_23 | AC | 1 ms
5,248 KB |
testcase_24 | AC | 1 ms
5,248 KB |
testcase_25 | AC | 1 ms
5,248 KB |
testcase_26 | AC | 1 ms
5,248 KB |
testcase_27 | AC | 1 ms
5,248 KB |
testcase_28 | AC | 1 ms
5,248 KB |
testcase_29 | AC | 1 ms
5,248 KB |
testcase_30 | AC | 1 ms
5,248 KB |
testcase_31 | AC | 1 ms
5,248 KB |
testcase_32 | AC | 1 ms
5,248 KB |
testcase_33 | AC | 1 ms
5,248 KB |
testcase_34 | AC | 1 ms
5,248 KB |
testcase_35 | AC | 1 ms
5,248 KB |
testcase_36 | AC | 1 ms
5,248 KB |
testcase_37 | AC | 1 ms
5,248 KB |
testcase_38 | AC | 1 ms
5,248 KB |
testcase_39 | AC | 1 ms
5,248 KB |
testcase_40 | AC | 1 ms
5,248 KB |
testcase_41 | AC | 1 ms
5,248 KB |
ソースコード
#[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(); }