結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
|
提出日時 | 2019-09-28 16:34:57 |
言語 | Rust (1.83.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#[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>whereT: 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>whereT: 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>whereT: 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>whereT: 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>whereF: 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();}