#414520 (Rust) No.336 門松列列

• 問題: No.336 門松列列
• ユーザー: akakimidori
• 提出日時: 2020-01-05 23:49:31
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 11 ms / 2,000 ms
• コード長: 3,023 bytes
• コンパイル時間: 14,475 ms
• コンパイル使用メモリ: 378,180 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-12 01:14:17
• 合計ジャッジ時間: 13,441 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	9 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	11 ms; 5,248 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	4 ms; 5,376 KB
testcase_08	AC	7 ms; 5,376 KB
testcase_09	AC	10 ms; 5,376 KB
testcase_10	AC	10 ms; 5,376 KB
testcase_11	AC	11 ms; 5,376 KB

ソースコード

// ---------- begin ModInt ----------
const MOD: u32 = 1_000_000_007;

#[derive(Clone, Copy)]
struct ModInt(u32);

impl std::ops::Add for ModInt {
    type Output = ModInt;
    fn add(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::AddAssign for ModInt {
    fn add_assign(&mut self, rhs: ModInt) {
        *self = *self + rhs;
    }
}

impl std::ops::Sub for ModInt {
    type Output = ModInt;
    fn sub(self, rhs: ModInt) -> Self::Output {
        let mut d = self.0 + MOD - rhs.0;
        if d >= MOD {
            d -= MOD;
        }
        ModInt(d)
    }
}

impl std::ops::SubAssign for ModInt {
    fn sub_assign(&mut self, rhs: ModInt) {
        *self = *self - rhs;
    }
}

impl std::ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, rhs: ModInt) -> Self::Output {
        ModInt((self.0 as u64 * rhs.0 as u64 % MOD as u64) as u32)
    }
}

impl std::ops::MulAssign for ModInt {
    fn mul_assign(&mut self, rhs: ModInt) {
        *self = *self * rhs;
    }
}

impl std::ops::Neg for ModInt {
    type Output = ModInt;
    fn neg(self) -> Self::Output {
        ModInt(if self.0 == 0 {0} else {MOD - self.0})
    }
}

impl std::fmt::Display for ModInt {
    fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

impl std::str::FromStr for ModInt {
    type Err = std::num::ParseIntError;
    fn from_str(s: &str) -> Result<Self, Self::Err> {
        let val = s.parse::<u32>()?;
        Ok(ModInt::new(val))
    }
}

#[allow(dead_code)]
impl ModInt {
    pub fn new(n: u32) -> ModInt {
        ModInt(n % MOD)
    }
    pub fn zero() -> ModInt {
        ModInt(0)
    }
    pub fn one() -> ModInt {
        ModInt(1)
    }
    pub fn pow(self, mut n: u32) -> ModInt {
        let mut t = ModInt::one();
        let mut s = self;
        while n > 0 {
            if n & 1 == 1 {
                t *= s;
            }
            s *= s;
            n >>= 1;
        }
        t
    }
    pub fn inv(self) -> ModInt {
        self.pow(MOD - 2)
    }
}
// ---------- end ModInt ----------

fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let n: usize = s.trim().parse().unwrap();
    if n <= 2 {
        println!("0");
        return;
    }
    let mut now = vec![(ModInt::one(), ModInt::one()); n];
    for _ in 1..n {
        let len = now.len();
        let mut next = vec![(ModInt::zero(), ModInt::zero()); len];
        for (i, &v) in now.iter().enumerate() {
            next[0].0 += v.1;
            next[i].0 -= v.1;
            next[i].1 += v.0;
        }
        let mut prev = next[0];
        for v in next[1..].iter_mut() {
            v.0 += prev.0;
            v.1 += prev.1;
            prev = *v;
        }
        next.truncate(len - 1);
        now = next;
    }
    let ans = now[0].0 + now[0].1;
    println!("{}", ans);
}

fn main() {
    run();
}