結果

問題 No.997 Jumping Kangaroo
コンテスト
ユーザー cotton_fn_
提出日時 2020-02-23 00:20:31
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 3,889 bytes
コンパイル時間 21,674 ms
コンパイル使用メモリ 401,576 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-10 01:16:38
合計ジャッジ時間 16,095 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused)]

use std::{
    fmt,
    io::{self, BufRead, Write},
    mem::{replace, swap},
    str::FromStr,
};

pub struct Input<R> {
    src: R,
    buf: Vec<u8>,
    pos: usize,
}

impl<R: BufRead> Input<R> {
    pub fn new(src: R) -> Self {
        Self {
            src,
            buf: Vec::new(),
            pos: 0,
        }
    }

    pub fn input_bytes(&mut self) -> &[u8] {
        loop {
            self.advance_while(|b| b.is_ascii_whitespace());
            if self.pos == self.buf.len() {
                self.buf.clear();
                self.src
                    .read_until(b'\n', &mut self.buf)
                    .expect("input error");
                self.pos = 0;
            } else {
                break;
            }
        }
        let l = self.pos;
        self.advance_while(|b| !b.is_ascii_whitespace());
        &self.buf[l..self.pos]
    }

    fn advance_while(&mut self, f: impl Fn(u8) -> bool) {
        while let Some(b) = self.buf.get(self.pos) {
            if !f(*b) {
                break;
            }
            self.pos += 1;
        }
    }

    pub fn input<T: InputParse>(&mut self) -> T {
        T::input(self)
    }
}

pub trait InputParse {
    fn input<R: BufRead>(input: &mut Input<R>) -> Self;
}

macro_rules! input_from_str_impls {
    { $($T:ty)* } => {
        $(
            impl InputParse for $T {
                fn input<R: BufRead>(input: &mut Input<R>) -> Self {
                    String::from_utf8_lossy(input.input_bytes())
                        .parse()
                        .expect("parse error")
                }
            }
        )*
    };
}

macro_rules! input_tuple_impls {
    { $(($($T:ident),+))* } => {
        $(
            impl<$($T: InputParse),+> InputParse for ($($T),+)
            {
                fn input<R: BufRead>(input: &mut Input<R>) -> Self {
                    ($(input.input::<$T>()),+)
                }
            }
        )*
    };
}

input_from_str_impls! {
    String char bool
    i8 i16 i32 i64 i128 isize
    u8 u16 u32 u64 u128 usize
    f32 f64
}

input_tuple_impls! {
    (A, B)
    (A, B, C)
    (A, B, C, D)
    (A, B, C, D, E)
    (A, B, C, D, E, F)
    (A, B, C, D, E, F, G)
}

pub fn mod_pow(mut a: i64, mut b: i64, m: i64) -> i64 {
    let mut y = 1;
    while b > 0 {
        if b & 1 == 1 {
            y = y * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    y
}

pub fn mod_inv(x: i64, m: i64) -> i64 {
    mod_pow(x, m - 2, m)
}

fn mul(ma: &[i64; 4], mb: &[i64; 4], mo: i64) -> [i64; 4] {
    let [a, b, c, d] = ma;
    let [s, t, u, v] = mb;
    [(a * s + b * u) % mo, (a * t + b * v) % mo, (c * s + d * u) % mo, (c * t + d * v) % mo]
}

fn pow(mat: &[i64; 4], mut k: i64, mo: i64) -> [i64; 4] {
    let mut res = [1, 0, 0, 1];
    let mut a = *mat;
    while k > 0 {
        if k & 1 == 1 {
            res = mul(&res, &a, mo);
        }
        a = mul(&a, &a, mo);
        k >>= 1;
    }
    res
}

fn main() {
    let stdin = io::stdin();
    let mut input = Input::new(stdin.lock());
    let stdout = io::stdout();
    let mut out = io::BufWriter::new(stdout.lock());
    let stderr = io::stderr();
    let mut err = io::BufWriter::new(stderr.lock());

    const MOD: i64 = 1e9 as i64 + 7;
    let (n, w, k): (i64, i64, i64) = input.input();
    let a: Vec<i64> = std::iter::repeat_with(|| input.input())
        .take(n as usize)
        .collect();

    let mut dp = vec![0; (2 * w + 1) as usize];
    dp[0] = 1;
    for i in 0..2 * w {
        for x in &a {
            if i + x <= 2 * w {
                dp[(i + x) as usize] += dp[i as usize];
                dp[(i + x) as usize] %= MOD;
            }
        }
    }

    let s1 = dp[w as usize];
    let s2 = (dp[2 * w as usize] - s1 * s1 % MOD + MOD) % MOD;

    let mat = [s1, s2, 1, 0];
    let res = pow(&mat, k, MOD);

    println!("{}", res[0]);
}
0