結果

問題 No.117 組み合わせの数
ユーザー Ratstar216
提出日時 2025-09-18 18:47:34
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 71 ms / 5,000 ms
コード長 3,782 bytes
コンパイル時間 12,565 ms
コンパイル使用メモリ 402,688 KB
実行使用メモリ 34,928 KB
最終ジャッジ日時 2025-09-18 18:47:48
合計ジャッジ時間 13,494 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{fastout, input};

pub fn mod_pow(mut a: i64, mut b: i64, modulus: i64) -> i64 {
    if modulus == 1 {
        return 0;
    }
    a = ((a % modulus) + modulus) % modulus;
    let mut result = 1;

    while b > 0 {
        if b & 1 == 1 {
            result = (result * a) % modulus;
        }
        a = (a * a) % modulus;
        b >>= 1;
    }
    result
}


pub fn factorial(n: usize, modulus: i64) -> i64 {
    if modulus == 1 {
        return 0;
    }

    let mut result = 1 % modulus;
    for i in 1..=n {
        result = (result * (i as i64 % modulus)) % modulus;
    }
    result
}

pub fn mod_inv(a: i64, modulus: i64) -> Option<i64> {
    let (g, x, _) = extended_gcd(a, modulus);
    if g != 1 && g != -1 {
        return None;
    }
    let inv = x.rem_euclid(modulus);
    Some(inv)
}

fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (g, x, y) = extended_gcd(b, a % b);
        (g, y, x - (a / b) * y)
    }
}

/// Pre-computes factorials and inverse factorials modulo a positive integer.
#[derive(Clone, Debug)]
pub struct ModCombinatorics {
    modulus: i64,
    fact: Vec<i64>,
    inv_fact: Vec<i64>,
}

impl ModCombinatorics {
    pub fn new(limit: usize, modulus: i64) -> Option<Self> {

        let mut fact = vec![1 % modulus; limit + 1];
        for i in 1..=limit {
            fact[i] = fact[i - 1] * (i as i64 % modulus) % modulus;
        }

        let mut inv_fact = vec![0; limit + 1];
        inv_fact[limit] = mod_inv(fact[limit], modulus)?;
        for i in (1..=limit).rev() {
            inv_fact[i - 1] = inv_fact[i] * (i as i64 % modulus) % modulus;
        }

        Some(Self {
            modulus,
            fact,
            inv_fact,
        })
    }

    pub fn modulus(&self) -> i64 {
        self.modulus
    }

    pub fn fact(&self, n: usize) -> i64 {
        self.fact[n]
    }

    /// Computes `nPk mod modulus` when `n >= k`.
    pub fn permutation(&self, n: usize, k: usize) -> Option<i64> {
        if k > n {
            return Some(0);
        }
        if n >= self.fact.len() {
            return None;
        }
        Some(self.fact[n] * self.inv_fact[n - k] % self.modulus)
    }

    pub fn combination(&self, n: usize, k: usize) -> Option<i64> {
        if k > n {
            return Some(0);
        }
        if n >= self.fact.len() {
            return None;
        }
        let numerator = self.fact[n];
        let denom = self.inv_fact[k] * self.inv_fact[n - k] % self.modulus;
        Some(numerator * denom % self.modulus)
    }


    pub fn homogeneous(&self, n: usize, k: usize) -> Option<i64> {
        if k == 0 {
            return Some(1);
        }
        if n == 0 {
            return Some(0);
        }
        let total = n.checked_add(k)?.checked_sub(1)?;
        if total >= self.fact.len() {
            return None;
        }
        self.combination(total, k)
    }
}

#[fastout]
fn main() {
    input! {
        t: usize
    }
    const MOD: i64 = 1_000_000_007;
    let comb = ModCombinatorics::new(2000000, MOD).unwrap();
    for _ in 0..t {
        input! {
            s: String
        }
        let open = s.find('(').unwrap();
        let comma = s.find(',').unwrap();
        let close = s.find(')').unwrap();

        let x = &s[..open];
        let a_str = &s[open+1 .. comma];
        let b_str = &s[comma+1 .. close];

        let a: usize = a_str.parse().unwrap();
        let b: usize = b_str.parse().unwrap();

        if x == "C" {
            println!("{}", comb.combination(a, b).unwrap());
        } else if x == "P" {
            println!("{}", comb.permutation(a, b).unwrap());
        } else if x == "H" {
            println!("{}", comb.homogeneous(a, b).unwrap());
        }
    }
}
0