結果

問題 No.533 Mysterious Stairs
コンテスト
ユーザー elphe
提出日時 2026-02-14 01:33:45
言語 Rust
(1.93.0 + proconio + num + itertools)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 875 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 30,634 ms
コンパイル使用メモリ 256,352 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2026-02-14 01:34:18
合計ジャッジ時間 32,266 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: u32,
    }

    println!("{}", output(solve(n)));
}

const fn prepare() -> [u32; 1_000_001] {
    let mut dp = [[0; 3]; 1_000_001];
    let mut ans = [0; 1_000_001];
    dp[0] = [0, 0, 0];
    ans[0] = 1;
    dp[1] = [1, 0, 0];
    ans[1] = 1;
    dp[2] = [0, 1, 0];
    ans[2] = 1;
    dp[3] = [1, 1, 1];
    ans[3] = 3;

    let mut i = 4;
    const MOD: u32 = 1_000_000_007;
    while i < 1_000_001 {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
        dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % MOD;
        dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % MOD;
        ans[i] = (dp[i][0] + dp[i][1] + dp[i][2]) % MOD;
        i += 1;
    }
    ans
}

fn solve(n: u32) -> u32 {
    const ANS: [u32; 1_000_001] = prepare();
    ANS[n as usize]
}

fn output(ans: u32) -> u32 {
    ans
}
0