結果

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

ソースコード

diff #
raw source code 

fn main() {
    let stdin = std::io::read_to_string(std::io::stdin().lock()).unwrap();
    let mut stdin = stdin.split_ascii_whitespace();

    let n: usize = stdin.next().unwrap().parse().unwrap();

    use std::io::Write;
    std::io::stdout()
        .lock()
        .write_all(output(solve(n)).as_bytes())
        .unwrap();
}

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: usize) -> u32 {
    const ANS: [u32; 1_000_001] = prepare();
    ANS[n]
}

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