結果

問題 No.117 組み合わせの数
ユーザー pianonekopianoneko
提出日時 2019-01-03 03:16:24
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 444 ms / 5,000 ms
コード長 3,913 bytes
コンパイル時間 14,014 ms
コンパイル使用メモリ 377,824 KB
実行使用メモリ 33,920 KB
最終ジャッジ日時 2024-11-22 13:37:28
合計ジャッジ時間 14,316 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 444 ms
33,920 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::collections::HashMap`
 --> src/main.rs:1:5
  |
1 | use std::collections::HashMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: function `lower_bound` is never used
  --> src/main.rs:34:4
   |
34 | fn lower_bound<T: Ord>(vec: &Vec<T>, x: T) -> usize {
   |    ^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `upper_bound` is never used
  --> src/main.rs:50:4
   |
50 | fn upper_bound<T: Ord>(vec: &Vec<T>, x: T) -> usize {
   |    ^^^^^^^^^^^

warning: structure field `MOD` should have a snake case name
  --> src/main.rs:67:5
   |
67 |     MOD: u64,
   |     ^^^
   |
   = note: `#[warn(non_snake_case)]` on by default
help: rename the identifier or convert it to a snake case raw identifier
   |
67 |     r#mod: u64,
   |     ~~~~~

warning: variable `MOD` should have a snake case name
  --> src/main.rs:74:13
   |
74 |         let MOD: u64 = 1_000_000_007;
   |             ^^^
   |
help: rename the identifier or convert it to a snake case raw identifier
   |
74 |         let r#mod: u64 = 1_000_000_007;
   |             ~~~~~

ソースコード

diff # 

use std::collections::HashMap;
use std::io::*;
use std::str::FromStr;
use std::string::String;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();

    token.parse().ok().expect("failed to parse token")
}

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {
        other.0.cmp(&self.0)
    }
}

fn lower_bound<T: Ord>(vec: &Vec<T>, x: T) -> usize {
    let (mut left, mut right): (i32, i32) = (-1, vec.len() as i32);

    while (right - left) > 1 {
        let mid = (right + left) / 2;

        if x <= vec[mid as usize] {
            right = mid;
        } else {
            left = mid;
        }
    }

    return right as usize;
}

fn upper_bound<T: Ord>(vec: &Vec<T>, x: T) -> usize {
    let (mut left, mut right): (i32, i32) = (-1, vec.len() as i32);

    while (right - left) > 1 {
        let mid = (right + left) / 2;

        if x < vec[mid as usize] {
            right = mid;
        } else {
            left = mid;
        }
    }

    return right as usize;
}

struct Combination {
    MOD: u64,
    fac: Vec<u64>,
    fac_inv: Vec<u64>,
}

impl Combination {
    pub fn new(n: u64) -> Self {
        let MOD: u64 = 1_000_000_007;
        let mut fac: Vec<u64> = vec![0; n as usize + 1];
        let mut fac_inv: Vec<u64> = vec![0; n as usize + 1];

        let get_inverse = |mut n: u64| -> u64 {
            let (mut res, mut p) = (1, MOD - 2);

            while p != 0 {
                if p & 1 == 1 {
                    res = (res * n) % MOD;
                }
                n = (n * n) % MOD;
                p >>= 1;
            }

            return res;
        };

        fac[0] = 1;

        for i in 1..n + 1 {
            fac[i as usize] = (fac[i as usize - 1] * i) % MOD;
        }

        for i in 0..n + 1 {
            fac_inv[i as usize] = get_inverse(fac[i as usize]);
        }

        Combination {
            MOD: MOD,
            fac: fac,
            fac_inv: fac_inv,
        }
    }

    fn get_comb(&self, n: u64, r: u64) -> u64 {
        if n < r {
            return 0;
        }

        let a: u64 = self.fac[n as usize];
        let b: u64 = self.fac_inv[(n - r) as usize];
        let c: u64 = self.fac_inv[r as usize];
        let bc: u64 = (b * c) % self.MOD;

        return (a * bc) % self.MOD;
    }

    fn get_perm(&self, n: u64, r: u64) -> u64 {
        if n < r {
            return 0;
        }

        let a: u64 = self.fac[n as usize];
        let b: u64 = self.fac_inv[(n - r) as usize];

        return (a * b) % self.MOD;
    }

    fn get_dupc(&self, n: u64, r: u64) -> u64 {
        if n == 0 && r == 0 {
            return 1;
        }

        return self.get_comb(n + r - 1, r);
    }
}

fn main() {
    let t: u64 = read();
    let comb = Combination::new(2_000_000);
    let ans: Vec<u64> = (0..t)
        .map(|_| {
            let mut input: String = read();
            let com = input.remove(0);

            input.pop();
            input.remove(0);

            let vec = input.split(',').collect::<Vec<_>>();
            let (n, r): (u64, u64) = (vec[0].parse().unwrap(), vec[1].parse().unwrap());

            if com == 'C' {
               return comb.get_comb(n, r);
            } else if com == 'P' {
                return comb.get_perm(n, r);
            } else {
                return comb.get_dupc(n, r);
            }
        })
        .collect();

    for x in ans {
        println!("{}", x);
    }
}
0