bouzuya.hatenablog.com

ぼうずやのにっき

二段の手すり / 唇をかんだ / ABC129 C を解いた

子どもと歩くようになって、手すりが上下二段になっている階段の価値が分かるようになった。……なったのだけど、なぜか下の子は背伸びして上の方の手すりを持ちたがる。子どもはそういうところがある。


口の中を噛んだ。よくやる。自覚はないけど、疲れているのかも……。たぶん噛むたびに思っている。

https://iris.to/note13plpyg27afrez75hjsusv09dtj7da4e8p2fnc6ev4qmzr67f7dfqelze38


use modint::ModInt1000000007 as ModInt;
use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [usize; m],
    }

    let mut ok = vec![true; n + 1];
    for a_i in a {
        ok[a_i] = false;
    }

    let mut dp = vec![ModInt::new(0); n + 1];
    dp[0] = ModInt::new(1);
    for i in 0..=n {
        for j in i + 1..=i + 2 {
            if j <= n && ok[j] {
                dp[j] = dp[j] + dp[i];
            }
        }
    }
    let ans = dp[n];
    println!("{}", ans);
}

// modint

今日のコミット。