結果

問題 No.3457 Fibo-shrink
コンテスト
ユーザー NakLon131
提出日時 2026-02-28 15:01:56
言語 Rust
(1.93.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 230 ms / 2,000 ms
コード長 1,567 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,210 ms
コンパイル使用メモリ 197,908 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-28 15:02:08
合計ジャッジ時間 4,384 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;

fn main() {
    input! {
        k: usize, // K日前までの総和
        s: usize, // 初項
        n: usize, // 調べる日数
    }

    // 重みを事前計算
    let mut fibo = vec![0; n+9];
    fibo[0] = 1;
    fibo[1] = 1;
    for i in 0..n {
        fibo[i+2] = mod_add(fibo[i], fibo[i+1]);
    }

// {
//     for i in 0..=n {
//         println!("{}", fibo[i]);
//     }
// }

    let mut ans_arr = vec![0; n+9];
    ans_arr[0] = s;

    for i in 1..n {
        let mut ret = 0;
        for kk in 1..=k+1 {
            if i >= kk {
                // ret += ans_arr[i-k] / fibo[i-k];
                let div = mod_div(ans_arr[i-kk], fibo[kk-1]);
                ret = mod_add(ret, div);
            }
        }
        ans_arr[i] = ret;
    }

// {
//     for i in 0..=n {
//         println!("{}", ans_arr[i]);
//     }

// }

    println!("{}", ans_arr[n-1]);
}

const MOD : usize = 10007;
#[allow(unused)]
fn mod_add(a: usize, b: usize) -> usize { let a = a % MOD; let b = b % MOD; (a + b) % MOD }
#[allow(unused)]
fn mod_sub(a: usize, b: usize) -> usize { let a = a % MOD; let b = b % MOD; (a + MOD - b) % MOD }
#[allow(unused)]
fn mod_mul(a: usize, b: usize) -> usize { let a = a % MOD; let b = b % MOD; (a * b) % MOD }
#[allow(unused)]
fn mod_div(a: usize, b: usize) -> usize { mod_mul(a, mod_pow(b, MOD-2)) }
#[allow(unused)]
fn mod_pow(mut a: usize, mut b: usize) -> usize {
    let mut ret = 1;
    while b > 0 {
        if b % 2 == 1 { ret = mod_mul(ret, a); }
        a = mod_mul(a, a);
        b /= 2;
    }
    ret
}
0