結果

問題 No.1172 Add Recursive Sequence
コンテスト
ユーザー noshi91
提出日時 2020-05-09 18:09:49
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 622 ms / 4,000 ms
コード長 2,164 bytes
コンパイル時間 16,473 ms
コンパイル使用メモリ 379,640 KB
実行使用メモリ 168,960 KB
最終ジャッジ日時 2024-10-08 20:14:34
合計ジャッジ時間 16,727 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;

struct Scanner<'a>(std::str::SplitWhitespace<'a>);

impl<'a> Scanner<'a> {
    fn new(s: &'a str) -> Self {
        Self(s.split_whitespace())
    }

    fn next<T>(&mut self) -> T
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
    {
        let s = self.0.next().expect("found EOF");
        match s.parse() {
            Ok(v) => v,
            Err(msg) => {
                println!(
                    "parse error. T = {}, s = \"{}\": {:?}",
                    std::any::type_name::<T>(),
                    s,
                    msg
                );
                panic!()
            }
        }
    }
}

const MOD: u64 = 1000000007;

fn normalize(mut x: i32) -> u64 {
    if x < 0 {
        x += MOD as i32;
    }
    return x as u64;
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = Scanner::new(&s);

    let k = sc.next::<usize>();
    let n = sc.next::<usize>();
    let m = sc.next::<usize>();
    let a = (0..k).map(|_| normalize(sc.next())).collect::<Vec<_>>();
    let c = (0..k).map(|_| normalize(sc.next())).collect::<Vec<_>>();

    let mut ls = vec![0; n + 1];
    let mut rs = vec![Vec::new(); n + 1];
    for _ in 0..m {
        let (l, r) = (sc.next::<usize>(), sc.next::<usize>());
        ls[l] += 1;
        rs[r].push(r - l);
    }

    let step = |seq: &mut Vec<u64>| {
        let next = (0..k).fold(0, |x, i| (x + c[i] * seq[k - 1 - i]) % MOD);
        seq.remove(0);
        seq.push(next);
    };

    let base = {
        let mut state = a.clone();
        (0..n)
            .map(move |_| {
                let res = state.clone();
                step(&mut state);
                res
            })
            .collect::<Vec<_>>()
    };

    let mut now = vec![0; k];

    for i in 0..n {
        step(&mut now);
        for j in 0..k {
            now[j] += ls[i] * a[j];
            now[j] %= MOD;
        }
        for &r in &rs[i] {
            for j in 0..k {
                now[j] += MOD - base[r][j];
                now[j] %= MOD;
            }
        }
        println!("{}", now[0]);
    }
}
0