結果

問題 No.891 隣接3項間の漸化式
ユーザー wesriverywesrivery
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#[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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0