結果

問題 No.1172 Add Recursive Sequence
ユーザー akakimidoriakakimidori
提出日時 2021-05-06 02:40:36
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,982 ms / 4,000 ms
コード長 1,580 bytes
コンパイル時間 12,767 ms
コンパイル使用メモリ 390,192 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 19:06:00
合計ジャッジ時間 19,724 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,812 KB
testcase_04 AC 1 ms
6,812 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 17 ms
6,944 KB
testcase_11 AC 15 ms
6,944 KB
testcase_12 AC 59 ms
6,940 KB
testcase_13 AC 52 ms
6,940 KB
testcase_14 AC 636 ms
6,940 KB
testcase_15 AC 1,864 ms
6,940 KB
testcase_16 AC 709 ms
6,940 KB
testcase_17 AC 1,982 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn read() -> (usize, Vec<u32>, Vec<u32>, Vec<(usize, usize)>) {
    let mut s = String::new();
    use std::io::Read;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let mut next = || it.next().unwrap().parse::<usize>().unwrap();
    let k = next();
    let n = next();
    let m = next();
    let mut a = vec![0; k];
    for a in a.iter_mut() {
        *a = next() as u32;
    }
    let mut c = vec![0; k];
    for c in c.iter_mut() {
        *c = next() as u32;
    }
    let mut p = vec![(0, 0); m];
    for p in p.iter_mut() {
        p.0 = next();
        p.1 = next();
    }
    (n, a, c, p)
}

const MOD: u32 = 1_000_000_007;

#[target_feature(enable = "avx2")]
unsafe fn add(a: &mut [u32], b: &[u32]) {
    for (a, b) in a.iter_mut().zip(b) {
        *a += *b;
        if *a >= MOD {
            *a -= MOD;
        }
    }
}

fn run() {
    let (n, a, c, p) = read();
    let mut dp = vec![0; n.max(a.len())];
    for (i, a) in a.iter().enumerate() {
        dp[i] = *a;
    }
    for i in a.len()..n {
        let mut s = 0;
        for (dp, c) in dp[..i].iter().rev().zip(&c) {
            s = ((s as u64 + *c as u64 * *dp as u64 ) % MOD as u64) as u32;
        }
        dp[i] = s;
    }
    let mut ans = vec![0; n];
    for (l, r) in p {
        unsafe {
            add(&mut ans[l..r], &dp);
        }
    }
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for a in ans {
        writeln!(out, "{}", a).ok();
    }
}

fn main() {
    run();
}
0