Struct MemorizedFactorial

Source

pub struct MemorizedFactorial<M>where
    M: MIntConvert<usize>,{
    pub fact: Vec<MInt<M>>,
    pub inv_fact: Vec<MInt<M>>,
}

Fields§

§fact: Vec<MInt<M>>§inv_fact: Vec<MInt<M>>

Implementations§

Source §

impl<M> MemorizedFactorial<M>
where M: MIntConvert<usize>,

Source

pub fn new(max_n: usize) -> Self

Examples found in repository ?

crates/competitive/src/math/formal_power_series/mod.rs (line 65)

64    fn memorized_factorial(n: usize) -> MemorizedFactorial<Self::Base> {
65        MemorizedFactorial::new(n)
66    }

More examples

Hide additional examples

crates/library_checker/src/enumerative_combinatorics/sharp_p_subset_sum.rs (line 11)

8pub fn sharp_p_subset_sum(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, t, s: [usize; iter n]);
11    let f = MemorizedFactorial::new(t);
12    let mut c = vec![M::zero(); t + 1];
13    for s in s {
14        c[s] += M::one();
15    }
16    let a = Fps998244353::from_vec(c).count_subset_sum(t + 1, |x| f.inv(x));
17    pp!(@it a.data[1..]);
18}

crates/library_checker/src/enumerative_combinatorics/binomial_coefficient_prime_mod.rs (line 10)

5pub fn binomial_coefficient_prime_mod(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(t, m: u32, nk: [(usize, usize); t]);
8    DynMIntU32::set_mod(m);
9    let max_n = nk.iter().map(|(n, _)| n).max().cloned().unwrap_or_default();
10    let f = MemorizedFactorial::new(max_n);
11    for (n, k) in nk {
12        let ans: DynMIntU32 = f.combination(n, k);
13        pp!(ans);
14    }
15}

crates/competitive/src/math/mint_matrix.rs (line 379)

371fn taylor_shift<M>(f: Vec<MInt<M>>, a: MInt<M>) -> Vec<MInt<M>>
372where
373    M: MIntConvert<usize>,
374{
375    let n = f.len();
376    if n == 0 {
377        return f;
378    }
379    let mf = MemorizedFactorial::new(n);
380    let mut res = vec![MInt::<M>::zero(); n];
381    let mut apow = vec![MInt::<M>::one(); n];
382    for i in 1..n {
383        apow[i] = apow[i - 1] * a;
384    }
385    for j in 0..n {
386        if f[j].is_zero() {
387            continue;
388        }
389        for k in 0..=j {
390            res[k] += f[j] * apow[j - k] * mf.combination(j, k);
391        }
392    }
393    res
394}

crates/competitive/src/math/binomial_prefix_sum.rs (line 74)

60    pub fn for_each<F>(self, mut f: F)
61    where
62        F: FnMut(usize, MInt<M>),
63    {
64        let query = &self.query;
65        if query.is_empty() {
66            return;
67        }
68        let max_n = query.iter().map(|&(_, n)| n).max().unwrap_or(0);
69        let modulus = M::mod_into();
70        debug_assert!(modulus > 2 && modulus % 2 == 1);
71        debug_assert!(max_n < modulus);
72        debug_assert!(query.iter().all(|&(m, n)| m <= n));
73
74        let fact = MemorizedFactorial::<M>::new(max_n);
75        let inv2 = MInt::<M>::from(2usize).inv();
76        let mut cur = MInt::<M>::one();
77        crate::mo_algorithm!(
78            query,
79            (m, n),
80            |old_m| cur += fact.combination(n, old_m + 1),
81            |new_m| cur -= fact.combination(n, new_m + 1),
82            |old_n| cur = cur + cur - fact.combination(old_n, m),
83            |new_n| cur = (cur + fact.combination(new_n, m)) * inv2,
84            |i| f(i, cur),
85        );
86    }

crates/library_checker/src/graph/counting_eulerian_circuits.rs (line 34)

9pub fn counting_eulerian_circuits(reader: impl Read, writer: impl Write) {
10    prepare_io!(reader, writer);
11    sc!(n, m, edges: [(usize, usize); iter m]);
12    let mut a = Matrix::<AddMulOperation<M>>::zeros((n, n));
13    let mut indegree = vec![0; n];
14    let mut outdegree = vec![0; n];
15    for (u, v) in edges {
16        a[u][v] -= M::from(1);
17        a[v][v] += M::from(1);
18        outdegree[u] += 1;
19        indegree[v] += 1;
20    }
21    if indegree != outdegree {
22        pp!(0);
23        return;
24    }
25    let root = outdegree.iter().position(|&d| d != 0).unwrap();
26    for i in 0..n {
27        a[root][i] = M::from(0);
28        a[i][root] = M::from(0);
29        if outdegree[i] == 0 {
30            a[i][i] = M::one();
31        }
32    }
33    a[root][root] = M::one();
34    let factorial = MemorizedFactorial::new(*outdegree.iter().max().unwrap() - 1);
35    let mut ans = a.determinant();
36    for d in outdegree {
37        if d != 0 {
38            ans *= factorial.fact[d - 1];
39        }
40    }
41    pp!(ans);
42}

Source

pub fn combination(&self, n: usize, r: usize) -> MInt<M>

Examples found in repository ?

crates/competitive/src/math/factorial.rs (line 52)

47    pub fn homogeneous_product(&self, n: usize, r: usize) -> MInt<M> {
48        debug_assert!(n + r < self.fact.len() + 1);
49        if n == 0 && r == 0 {
50            MInt::one()
51        } else {
52            self.combination(n + r - 1, r)
53        }
54    }

More examples

Hide additional examples

crates/library_checker/src/enumerative_combinatorics/binomial_coefficient_prime_mod.rs (line 12)

5pub fn binomial_coefficient_prime_mod(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(t, m: u32, nk: [(usize, usize); t]);
8    DynMIntU32::set_mod(m);
9    let max_n = nk.iter().map(|(n, _)| n).max().cloned().unwrap_or_default();
10    let f = MemorizedFactorial::new(max_n);
11    for (n, k) in nk {
12        let ans: DynMIntU32 = f.combination(n, k);
13        pp!(ans);
14    }
15}

crates/competitive/src/math/mint_matrix.rs (line 390)

371fn taylor_shift<M>(f: Vec<MInt<M>>, a: MInt<M>) -> Vec<MInt<M>>
372where
373    M: MIntConvert<usize>,
374{
375    let n = f.len();
376    if n == 0 {
377        return f;
378    }
379    let mf = MemorizedFactorial::new(n);
380    let mut res = vec![MInt::<M>::zero(); n];
381    let mut apow = vec![MInt::<M>::one(); n];
382    for i in 1..n {
383        apow[i] = apow[i - 1] * a;
384    }
385    for j in 0..n {
386        if f[j].is_zero() {
387            continue;
388        }
389        for k in 0..=j {
390            res[k] += f[j] * apow[j - k] * mf.combination(j, k);
391        }
392    }
393    res
394}

crates/competitive/src/math/binomial_prefix_sum.rs (line 80)

60    pub fn for_each<F>(self, mut f: F)
61    where
62        F: FnMut(usize, MInt<M>),
63    {
64        let query = &self.query;
65        if query.is_empty() {
66            return;
67        }
68        let max_n = query.iter().map(|&(_, n)| n).max().unwrap_or(0);
69        let modulus = M::mod_into();
70        debug_assert!(modulus > 2 && modulus % 2 == 1);
71        debug_assert!(max_n < modulus);
72        debug_assert!(query.iter().all(|&(m, n)| m <= n));
73
74        let fact = MemorizedFactorial::<M>::new(max_n);
75        let inv2 = MInt::<M>::from(2usize).inv();
76        let mut cur = MInt::<M>::one();
77        crate::mo_algorithm!(
78            query,
79            (m, n),
80            |old_m| cur += fact.combination(n, old_m + 1),
81            |new_m| cur -= fact.combination(n, new_m + 1),
82            |old_n| cur = cur + cur - fact.combination(old_n, m),
83            |new_n| cur = (cur + fact.combination(new_n, m)) * inv2,
84            |i| f(i, cur),
85        );
86    }

Source

pub fn permutation(&self, n: usize, r: usize) -> MInt<M>

Source

pub fn homogeneous_product(&self, n: usize, r: usize) -> MInt<M>

Source

pub fn inv(&self, n: usize) -> MInt<M>

Examples found in repository ?

crates/competitive/src/math/formal_power_series/mod.rs (line 87)

86    fn memorized_inv(mf: &MemorizedFactorial<Self::Base>, n: usize) -> Self {
87        mf.inv(n)
88    }

More examples

Hide additional examples

crates/library_checker/src/enumerative_combinatorics/sharp_p_subset_sum.rs (line 16)

8pub fn sharp_p_subset_sum(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, t, s: [usize; iter n]);
11    let f = MemorizedFactorial::new(t);
12    let mut c = vec![M::zero(); t + 1];
13    for s in s {
14        c[s] += M::one();
15    }
16    let a = Fps998244353::from_vec(c).count_subset_sum(t + 1, |x| f.inv(x));
17    pp!(@it a.data[1..]);
18}