結果

問題 No.660 家を通り過ぎないランダムウォーク問題
ユーザー zeronosu77108zeronosu77108
提出日時 2022-02-21 14:54:57
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
17,532 KB
testcase_01 AC 18 ms
17,476 KB
testcase_02 AC 18 ms
17,460 KB
testcase_03 AC 18 ms
17,492 KB
testcase_04 AC 17 ms
17,524 KB
testcase_05 AC 17 ms
17,304 KB
testcase_06 AC 18 ms
17,472 KB
testcase_07 AC 19 ms
17,408 KB
testcase_08 AC 19 ms
17,476 KB
testcase_09 AC 19 ms
17,508 KB
testcase_10 AC 18 ms
17,528 KB
testcase_11 AC 18 ms
17,408 KB
testcase_12 AC 17 ms
17,652 KB
testcase_13 AC 18 ms
17,536 KB
testcase_14 AC 18 ms
17,416 KB
testcase_15 AC 17 ms
17,496 KB
testcase_16 AC 19 ms
17,532 KB
testcase_17 AC 18 ms
17,508 KB
testcase_18 AC 18 ms
17,456 KB
testcase_19 AC 19 ms
17,536 KB
testcase_20 AC 18 ms
17,436 KB
testcase_21 AC 17 ms
17,536 KB
testcase_22 AC 17 ms
17,464 KB
testcase_23 AC 17 ms
17,428 KB
testcase_24 AC 17 ms
17,536 KB
testcase_25 AC 19 ms
17,652 KB
testcase_26 AC 18 ms
17,416 KB
testcase_27 AC 17 ms
17,536 KB
testcase_28 AC 18 ms
17,528 KB
testcase_29 AC 18 ms
17,536 KB
testcase_30 AC 18 ms
17,408 KB
testcase_31 AC 19 ms
17,408 KB
testcase_32 AC 18 ms
17,536 KB
testcase_33 AC 17 ms
17,536 KB
testcase_34 AC 19 ms
17,296 KB
testcase_35 AC 19 ms
17,528 KB
testcase_36 AC 19 ms
17,536 KB
testcase_37 AC 18 ms
17,524 KB
testcase_38 AC 19 ms
17,408 KB
testcase_39 AC 18 ms
17,300 KB
testcase_40 AC 19 ms
17,428 KB
testcase_41 AC 19 ms
17,432 KB
testcase_42 AC 19 ms
17,428 KB
testcase_43 AC 20 ms
17,484 KB
testcase_44 AC 20 ms
17,292 KB
権限があれば一括ダウンロードができます

ソースコード

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