結果
問題 | No.1172 Add Recursive Sequence |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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]); } }