結果

問題 No.660 家を通り過ぎないランダムウォーク問題
コンテスト
ユーザー zeronosu77108
提出日時 2022-02-21 14:54:57
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 20 ms / 2,000 ms
コード長 3,305 bytes
コンパイル時間 13,263 ms
コンパイル使用メモリ 378,120 KB
実行使用メモリ 17,652 KB
最終ジャッジ日時 2024-06-29 19:30:31
合計ジャッジ時間 15,764 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    let n : i64 = input();
    const MOD : usize = 1_000_000_007;

    let comb = Combination::new((1_000_000) as usize);
    let mut ans = 0;

    for i in (n..=2*n).step_by(2) {
        let t = (i - 1) as usize;
        let r1 = (((i-1)-n+1)/2).abs() as usize;
        let r2 = (((i-1)+2*n - n + 1)/2) as usize;
        ans += comb.nCr(t, r1) + MOD - comb.nCr(t, r2);
        ans %= MOD;
    }

    println!("{}", ans);
}


struct Combination { n:usize, fac:Vec<usize>, ifac:Vec<usize>} impl Combination { const MOD : usize = 1_000_000_007; pub fn new(n:usize) -> Self { let mut fac = vec![1; n+1]; for i in 1..=n { fac[i] = fac[i-1] * i % Self::MOD; } let mut ifac = vec![Self::pow(fac[n], Self::MOD-2); n+1]; for i in (1..=n).rev() { ifac[i-1] = ifac[i] * i % Self::MOD; } Self { n:n+1, fac, ifac } } #[allow(non_snake_case, dead_code)] pub fn nCr(&self, n:usize, r:usize) -> usize { assert!(n <= self.n); assert!(r <= self.n); if n < r { 0 } else { self.fac[n] * self.ifac[r] % Self::MOD * self.ifac[n-r] % Self::MOD } } #[allow(non_snake_case, dead_code)] pub fn nPr(&self, n:usize, r:usize) -> usize { assert!(n <= self.n); assert!(r <= self.n); if n < r { 0 } else { self.fac[n] * self.ifac[n-r] % Self::MOD } } pub fn pow(mut n:usize, mut x:usize) -> usize { let mut res = 1; while x!=0 { if x%2 == 1 { res *= n; res %= Self::MOD; } n*=n; n%=Self::MOD; x /= 2; } res } }
#[allow(dead_code)]
fn input<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn input_t<T: std::str::FromStr, U: std::str::FromStr>() -> (T, U) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let s = s.trim().split_whitespace().collect::<Vec<&str>>();
    (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap())
}

#[allow(dead_code)]
fn input_t3<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr>() -> (T1, T2, T3) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let s = s.trim().split_whitespace().collect::<Vec<&str>>();
    (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap())
}

#[allow(dead_code)]
fn input_t4<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr>() -> (T1, T2, T3, T4) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let s = s.trim().split_whitespace().collect::<Vec<&str>>();
    (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap())
}

#[allow(dead_code)]
fn input_t5<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr, T5: std::str::FromStr>() -> (T1, T2, T3, T4, T5) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let s = s.trim().split_whitespace().collect::<Vec<&str>>();
    (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap(), s[4].parse().ok().unwrap())
}

#[allow(dead_code)]
fn input_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect()
}
0