dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

use std::ops::*;

use crate::{
    factorial_table_from_u64::factorial_table,
    inverse_factorial_table_from_u64::inverse_factorial_table,
};

pub struct Combination<T> {
    fact: Vec<T>,
    inv_fact: Vec<T>,
}

impl<T> Combination<T>
where
    T: Mul<Output = T> + From<u64> + Clone,
{
    pub fn new(size: usize) -> Self
    where
        T: Div<Output = T>,
    {
        Self {
            fact: factorial_table::<T>(size),
            inv_fact: inverse_factorial_table::<T>(size),
        }
    }

    pub fn calc(
        &self,
        n: usize,
        k: usize,
    ) -> T {
        if k > n {
            return 0.into();
        }

        self.fact[n].clone()
            * self.inv_fact[n - k].clone()
            * self.inv_fact[k].clone()
    }

    pub fn inv(
        &self,
        n: usize,
        k: usize,
    ) -> T {
        assert!(k <= n); // (n, k) := 0 if k > n, so the inverse is undefined.
        self.inv_fact[n].clone()
            * self.fact[k].clone()
            * self.fact[n - k].clone()
    }
}

// #[cfg(test)]
mod tests {

    #[test]

    fn test() {
        use super::*;
        use crate::{
            default_static_modular_arithmetic::Modular1_000_000_007,
            modular_int_with_arithmetic::Modint,
        };

        type Mint = Modint<u32, Modular1_000_000_007>;

        let choose = Combination::<Mint>::new(100);

        assert_eq!(choose.calc(5, 2), 10.into());
    }
}