結果

問題 No.1105 Many Triplets
コンテスト
ユーザー Strorkis
提出日時 2020-07-05 19:38:10
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,257 bytes
コンパイル時間 14,142 ms
コンパイル使用メモリ 396,384 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 18:56:14
合計ジャッジ時間 15,413 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::ops::{Mul, MulAssign};

#[derive(Clone)]
struct Matrix {
    a: Vec<Vec<usize>>,
}

impl Matrix {
    const MOD: usize = 1_000_000_007;

    fn new(a: Vec<Vec<usize>>) -> Matrix {
        Matrix { a }
    }

    fn pow(self, mut n: usize) -> Matrix {
        let p = self.a.len();

        let mut a = vec![vec![0; p]; p];
        for i in 0..p {
            a[i][i] = 1;
        }

        let mut res = Matrix { a };
        let mut x = self.clone();

        while n > 0 {
            if n & 1 == 1 { res *= x.clone(); }
            x *= x.clone();
            n >>= 1;
        }

        res
    }
}

impl Mul for Matrix {
    type Output = Matrix;

    fn mul(self, other: Matrix) -> Matrix {
        let p = self.a.len();
        let q = other.a[0].len();
        let r = other.a.len();

        let mut a = vec![vec![0; q]; p];

        for i in 0..p {
            for j in 0..q {
                for k in 0..r {
                    a[i][j] += self.a[i][k] * other.a[k][j] % Matrix::MOD;
                    a[i][j] %= Matrix::MOD;
                }
            }
        }

        Matrix { a }
    }
}

impl MulAssign for Matrix {
    fn mul_assign(&mut self, rhs: Matrix) {
        *self = (*self).clone() * rhs;
    }
}

fn main() {
    const MOD: usize = 1_000_000_007;

    let n: usize = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        buf.trim_end().parse().unwrap()
    };

    let [a, b, c]: [usize; 3] = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        [
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        ]
    };

    let x = {
        Matrix::new(
            vec![
                vec![1, MOD - 1, 0],
                vec![0, 1, MOD - 1],
                vec![MOD - 1, 0, 1],
            ]
        )
    };
    let x = x.pow(n - 1);
    let ans = x * Matrix::new(vec![vec![a], vec![b], vec![c]]);
    println!(
        "{}",
        ans.a
            .iter()
            .map(|x| x[0].to_string())
            .collect::<Vec<_>>()
            .join(" ")
    );
}
0