結果

問題 No.660 家を通り過ぎないランダムウォーク問題
ユーザー 👑 zeronosu77108zeronosu77108
提出日時 2022-02-21 14:54:57
言語 Rust
(1.77.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 3,305 bytes
コンパイル時間 2,184 ms
コンパイル使用メモリ 136,220 KB
実行使用メモリ 17,580 KB
最終ジャッジ日時 2023-09-12 06:26:16
合計ジャッジ時間 5,007 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
17,540 KB
testcase_01 AC 17 ms
17,552 KB
testcase_02 AC 17 ms
17,500 KB
testcase_03 AC 17 ms
17,396 KB
testcase_04 AC 17 ms
17,380 KB
testcase_05 AC 16 ms
17,540 KB
testcase_06 AC 16 ms
17,568 KB
testcase_07 AC 17 ms
17,564 KB
testcase_08 AC 17 ms
17,392 KB
testcase_09 AC 17 ms
17,356 KB
testcase_10 AC 17 ms
17,356 KB
testcase_11 AC 16 ms
17,540 KB
testcase_12 AC 17 ms
17,380 KB
testcase_13 AC 17 ms
17,536 KB
testcase_14 AC 18 ms
17,356 KB
testcase_15 AC 17 ms
17,392 KB
testcase_16 AC 17 ms
17,384 KB
testcase_17 AC 17 ms
17,580 KB
testcase_18 AC 18 ms
17,344 KB
testcase_19 AC 18 ms
17,384 KB
testcase_20 AC 17 ms
17,392 KB
testcase_21 AC 17 ms
17,544 KB
testcase_22 AC 17 ms
17,388 KB
testcase_23 AC 17 ms
17,400 KB
testcase_24 AC 17 ms
17,340 KB
testcase_25 AC 17 ms
17,396 KB
testcase_26 AC 18 ms
17,304 KB
testcase_27 AC 17 ms
17,536 KB
testcase_28 AC 16 ms
17,572 KB
testcase_29 AC 18 ms
17,380 KB
testcase_30 AC 17 ms
17,300 KB
testcase_31 AC 17 ms
17,544 KB
testcase_32 AC 18 ms
17,408 KB
testcase_33 AC 17 ms
17,540 KB
testcase_34 AC 17 ms
17,412 KB
testcase_35 AC 17 ms
17,496 KB
testcase_36 AC 17 ms
17,368 KB
testcase_37 AC 17 ms
17,572 KB
testcase_38 AC 18 ms
17,580 KB
testcase_39 AC 17 ms
17,540 KB
testcase_40 AC 19 ms
17,400 KB
testcase_41 AC 18 ms
17,580 KB
testcase_42 AC 19 ms
17,580 KB
testcase_43 AC 19 ms
17,392 KB
testcase_44 AC 18 ms
17,408 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